Game of Life
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 complication 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, so the result would differ from applying all updates at once. We need a way to read the original state of every cell while writing the new states.
The four rules reduce to two conditions for a cell being alive in the next generation:
- 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
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. Since every neighbor count comes from the unmodified copy, the order in which we update cells no longer matters.
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 is easy to reason about, but it uses O(m * n) extra space to store the whole board. The follow-up asks for an in-place solution. Each cell is stored as an integer but carries only one bit of information (0 or 1), so the unused bits can hold a second value. The next approach uses them to store both the old and the new state in the same cell.
Approach 2: In-Place with State Encoding (Optimal)
Intuition
Each cell holds one bit of state but is stored as an int, leaving room to record a transition instead of a single value. Use four 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)
The original state is recoverable as value % 2: 0 % 2 = 0 (dead), 1 % 2 = 1 (alive), 2 % 2 = 0 (dead), 3 % 2 = 1 (alive). The two even codes mean "was dead" and the two odd codes mean "was alive."
After the first pass encodes all transitions, a second pass converts to final states: 0 and 3 become 0 (dead), 1 and 2 become 1 (alive).
The simultaneous-update requirement holds because neighbor counts always reflect original states. When a cell is processed, some of its neighbors are still raw (0 or 1) and others were already encoded (2 or 3). Reading every neighbor as value % 2 recovers its original bit in both cases (2 % 2 = 0, 3 % 2 = 1), so an encoded neighbor counts the same as it would have before encoding. The encoding never changes a cell's parity until the second pass, which only runs after every count is finished.
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.
This is already optimal at O(m * n) time and O(1) space. The next approach reaches the same bounds with a more systematic encoding: instead of four chosen integers, it stores the next state in a separate bit of each cell.
Approach 3: Bit Manipulation (Alternative Optimal)
Intuition
Use the bits of each integer directly. Bit 0 (the least significant bit) holds the original state, which is already there. Bit 1 holds the next state, which we compute and set.
- Bit 0 = current state (already there)
- Bit 1 = next state (computed and set during the pass)
To read the original state of any cell, mask with board[r][c] & 1. To set the next state to alive, set bit 1 with board[r][c] |= 2. After processing every cell, right-shift each value by 1 so the next state becomes the current state.
Unlike Approach 2, the two states live in fixed, separate bits rather than four chosen integers, so reading the original state never depends on the modulo trick.
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.