Game of Life
Problem
Given a 2D board representing the current state of cells (1 for live, 0 for dead), update the board to the next state according to the Game of Life rules simultaneously for all cells.
- m == board.length
- n == board[i].length
- 1 ≤ m, n ≤ 25
- board[i][j] is 0 or 1
Example
board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]][[0,0,0],[1,0,1],[0,1,1],[0,1,0]]Starting with the given board, the algorithm counts live neighbors for each cell. For example, the cell at (1,0) is dead but has exactly three live neighbors, so it becomes live (value 1). The cell at (0,1) is live but has only one live neighbor, so it dies (value 0). The algorithm uses temporary markers (-1 for live-to-dead, 2 for dead-to-live) to track transitions without affecting neighbor counts. After processing all cells, it finalizes the board by converting temporary markers to their final states.
Approach
Straightforward Solution
A naive approach would create a copy of the board to compute the next state, then copy it back. This uses O(m*n) extra space, which is inefficient for large boards.
Core Observation
The next state of each cell depends on the count of live neighbors, but all updates must happen simultaneously. This means the algorithm cannot update the board in-place naively, as changes would affect neighbor counts of other cells.
Path to Optimal
PreviewThe key insight is to encode state transitions in-place using temporary markers that distinguish between original and next states…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewTraverse each cell, count live neighbors by checking all eight directions and considering cells with absolute value 1 as originally live. Apply the rules and mark transitions with temporary values (-1 for live-to-dead, 2 for dead-to-live)…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(m * n)
Each cell is visited twice: once to compute neighbor counts and mark transitions, and once to finalize states. Each neighbor check is constant time (8 directions), so total time is proportional to the number of cells.
Space
O(1)
The algorithm uses only a fixed set of temporary markers and a constant-size directions array, modifying the board in-place without additional data structures proportional to input size.
Pattern Spotlight
Matrix Traversal (In-Place State Encoding)
When simultaneous updates depend on neighbors' original states, encode transitions with temporary markers that preserve original information during traversal, enabling in-place updates without extra space.
Solution
| 1 | class Solution: |
| 2 | def gameOfLife(self, board: List[List[int]]) -> None: |
| 3 | rows = len(board) |
| 4 | cols = len(board[0]) |
| 5 | |
| 6 | directions = [ |
| 7 | (-1, -1), (-1, 0), (-1, 1), |
| 8 | (0, -1), (0, 1), |
| 9 | (1, -1), (1, 0), (1, 1) |
| 10 | ] |
| 11 | |
| 12 | for r in range(rows): |
| 13 | for c in range(cols): |
| 14 | live_neighbors = 0 |
| 15 | |
| 16 | for dr, dc in directions: |
| 17 | nr = r + dr |
| 18 | nc = c + dc |
| 19 | |
| 20 | if 0 <= nr < rows and 0 <= nc < cols and abs(board[nr][nc]) == 1: |
| 21 | live_neighbors += 1 |
| 22 | |
| 23 | if board[r][c] == 1 and (live_neighbors < 2 or live_neighbors > 3): |
| 24 | board[r][c] = -1 |
| 25 | |
| 26 | if board[r][c] == 0 and live_neighbors == 3: |
| 27 | board[r][c] = 2 |
| 28 | |
| 29 | for r in range(rows): |
| 30 | for c in range(cols): |
| 31 | if board[r][c] > 0: |
| 32 | board[r][c] = 1 |
| 33 | else: |
| 34 | board[r][c] = 0 |
Step-by-Step Solution
Count Live Neighbors and Mark State Transitions In-Place
| 3 | rows = len(board) |
| 4 | cols = len(board[0]) |
| 6 | directions = [ |
| 7 | (-1, -1), (-1, 0), (-1, 1), |
| 8 | (0, -1), (0, 1), |
| 9 | (1, -1), (1, 0), (1, 1) |
| 12 | for r in range(rows): |
| 13 | for c in range(cols): |
| 14 | live_neighbors = 0 |
| 16 | for dr, dc in directions: |
| 17 | nr = r + dr |
| 18 | nc = c + dc |
| 20 | if 0 <= nr < rows and 0 <= nc < cols and abs(board[nr][nc]) == 1: |
| 21 | live_neighbors += 1 |
| 23 | if board[r][c] == 1 and (live_neighbors < 2 or live_neighbors > 3): |
| 24 | board[r][c] = -1 |
| 26 | if board[r][c] == 0 and live_neighbors == 3: |
| 27 | board[r][c] = 2 |
Objective
To iterate over each cell, count its live neighbors considering original states, and mark cells with temporary values to indicate state changes without losing original information.
Key Insight
Using the absolute value of cell states allows the algorithm to distinguish originally live cells (abs == 1) from dead ones, even after marking transitions. This enables accurate neighbor counts while performing in-place updates. Marking live-to-dead as -1 and dead-to-live as 2 encodes transitions without interfering with neighbor calculations.
Interview Quick-Check
Core Logic
Count live neighbors by checking all eight directions and using abs(board[nr][nc]) == 1 to identify originally live cells, ensuring neighbor counts remain accurate despite in-place updates.
State & Boundaries
Check boundary conditions for neighbors (0 <= nr < rows and 0 <= nc < cols) to avoid index errors.
Common Pitfalls & Bugs
Failing to use absolute values when counting neighbors leads to incorrect counts because temporary markers (-1, 2) would be misinterpreted.
Complexity
This step runs in O(m*n) time, with a constant factor of 8 for neighbor checks, which is efficient for the problem constraints.
Finalize Board by Converting Temporary Markers to Final States
To traverse the board again and convert all temporary markers to their final live or dead states, completing the simultaneous update.
1 more step with full analysis available on Pro.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
if 0 <= nr < rows and 0 <= nc < cols and abs(board[nr][nc]) == 1:Check if neighbor is within board boundaries and originally live.
This condition is critical because it preserves the original state information during in-place updates, enabling accurate neighbor counts even when cells have been marked for state changes.
if board[r][c] == 1 and (live_neighbors < 2 or live_neighbors > 3):Mark live cells that die due to underpopulation or overpopulation.
Marking with -1 allows the algorithm to distinguish cells that were originally live but will die, preserving original state information for neighbor counts while encoding the next state.
if board[r][c] == 0 and live_neighbors == 3:Mark dead cells that become live due to reproduction.
Marking with 2 allows the algorithm to distinguish cells that were originally dead but will become live, enabling simultaneous updates without corrupting neighbor counts.
Full line-by-line criticality + rationale for all 24 lines available on Pro.
Test Your Understanding
Why does the algorithm use temporary markers like -1 and 2 instead of directly updating cells to 0 or 1 during the first pass?
See the answer with Pro.
Related Problems
Matrix Traversal pattern
Don't just read it. Drill it.
Reconstruct Game of Life from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Game of Life drill