Game of Life
Last Updated: March 22, 2026
Understanding the Problem
We have a 2D grid where each cell is either alive (1) or dead (0). We need to apply four rules to every cell at the same time to produce the next generation.
The tricky part is the word "simultaneously." If we update cell (0,0) first and then move on to cell (0,1), cell (0,1)'s neighbors have already changed. The result would be different from applying all updates at once. So we need a way to read the original state while writing the new state, and that's the core challenge here.
If you simplify the four rules, they reduce to just two conditions for the next state being alive:
- A live cell survives if it has exactly 2 or 3 live neighbors.
- A dead cell becomes alive if it has exactly 3 live neighbors.
In all other cases, the cell is dead in the next generation.
Approach 1: Brute Force (Copy Board)
Intuition
The most straightforward way to handle the simultaneous update is to just make a copy of the board. Read neighbor counts from the copy (which never changes), and write the new states directly to the original board. This completely avoids the corruption problem because we're always reading from the pristine original.
Algorithm
- Create a deep copy of the board.
- For each cell in the board, count its live neighbors using the copy.
- Apply the four rules to determine the cell's next state, and write it to the original board.
- The original board now reflects the next generation.
Example Walkthrough
Code
- Time Complexity: O(m * n). We visit each cell once and check at most 8 neighbors per cell. Since 8 is a constant, the overall work is proportional to the number of cells.
- Space Complexity: O(m * n). We create a full copy of the board to preserve original states.
The copy-based approach works perfectly and is easy to understand, but we're using O(m * n) extra space to store the entire board. The follow-up question explicitly asks: can you do this in-place? The problem gives us a hint, each cell is stored as an integer but only uses one bit (0 or 1). What if we used the remaining bits to encode both the old and new state in the same cell?
Approach 2: In-Place with State Encoding (Optimal)
Intuition
Here's the key insight: each cell only needs one bit (0 or 1), but it's stored as an int. We have plenty of room to encode extra information. What if we used different numbers to represent the four possible transitions?
0-> was dead, stays dead (dead -> dead)1-> was alive, stays alive (alive -> alive)2-> was dead, now alive (dead -> alive)3-> was alive, now dead (alive -> dead)
With this encoding, the original state is always value % 2. So 0 % 2 = 0 (originally dead), 1 % 2 = 1 (originally alive), 2 % 2 = 0 (originally dead), 3 % 2 = 1 (originally alive). This means even after encoding a cell, its neighbors can still read the original state using % 2.
After the first pass encodes all transitions, a second pass converts to final states: values 0 and 3 become 0 (dead), values 1 and 2 become 1 (alive).
The encoding scheme works because % 2 always recovers the original state. When we process cells in order, some neighbors have already been encoded (e.g., they might be 2 or 3 instead of 0 or 1). But since 2 % 2 = 0 (originally dead) and 3 % 2 = 1 (originally alive), the neighbor count is always based on original states, not the new ones. This is what makes the simultaneous update possible without a copy.
Algorithm
- First pass: for each cell, count live neighbors using
board[r][c] % 2to get the original state (this works even for already-encoded cells). - Based on the count and the cell's current state, encode the transition:
- If the cell is alive (value % 2 == 1) and it dies, set it to 3.
- If the cell is dead (value % 2 == 0) and it becomes alive, set it to 2.
- Otherwise, leave it as-is (0 stays 0, 1 stays 1).
- Second pass: convert encoded values to final states. Values 0 and 3 become 0 (dead), values 1 and 2 become 1 (alive).
Example Walkthrough
Code
- Time Complexity: O(m * n). Two passes over the board, each visiting every cell. Each cell checks at most 8 neighbors, which is constant work.
- Space Complexity: O(1). We modify the board in-place using encoded values. No extra data structures needed beyond a few variables.
The state encoding approach is already optimal at O(m * n) time and O(1) space. But there's an alternative way to think about the in-place encoding that uses bit manipulation instead of arbitrary state values. What if we made the encoding more systematic by storing the next state in the second bit of each cell?
Approach 3: Bit Manipulation (Alternative Optimal)
Intuition
Instead of inventing an arbitrary encoding, we can use the bits of each integer directly. The original state is stored in bit 0 (the least significant bit). We'll store the next state in bit 1 (the second bit).
- Bit 0 = current state (already there)
- Bit 1 = next state (we compute and set this)
To read the original state of any cell, we use board[r][c] & 1. To set the next state, we use board[r][c] |= (nextState << 1). After processing all cells, we right-shift every value by 1 to make the next state the current state.
This is conceptually cleaner than Approach 2 because the encoding isn't arbitrary. It's a direct application of bit-level storage.
Algorithm
- For each cell, count live neighbors using
board[r][c] & 1(reads only the original state from bit 0). - Determine the next state based on the rules.
- If the next state is alive, set bit 1:
board[i][j] |= 2. - After processing all cells, right-shift every value by 1:
board[i][j] >>= 1.
Example Walkthrough
Code
- Time Complexity: O(m * n). Same as Approach 2. Two passes, constant work per cell.
- Space Complexity: O(1). In-place modification using bit manipulation. No extra data structures.