Problem editorial

Game of Life

MediumArray/Matrix Manipulation PatternsArray

Editorial

Core insight

Game of Life · Array/Matrix Manipulation Patterns

Core Insight for Game of Life

The core insight that allows us to move from the brute force approach to the optimal pattern is the observation that the input data only utilizes the values 0 and 1. However, an integer (in C++, Java, or Python) can hold a much wider range of values.

We can invent new "composite" states that encode both the past (current generation) and the future (next generation). By defining unique integers for state transitions, we can update the board in a single pass without losing the information required for neighbors that haven't been processed yet.

Visual Description: Imagine the grid as a state machine. Instead of flipping a 1 directly to a 0, we flip it to a temporary marker, let's say 2.

If a cell holds 2, it tells us: "I am currently live (1) for calculation purposes, but I will be dead (0) in the next frame."
If a cell holds 3, it tells us: "I am currently dead (0) for calculation purposes, but I will be live (1) in the next frame."

By reading the "past" part of the code during neighbor counting and writing the "future" part of the code during the update, we simulate simultaneity in-place.

Deep dive

Full breakdown

Full reasoning, pitfalls, and implementation flow

LeetCode 289: Game of Life Solution & Explanation

Problem Overview

TL;DR: The optimal solution uses in-place marking with temporary state codes to simulate simultaneous updates without allocating extra memory for a board copy.

The Game of Life is a cellular automaton played on an m x n grid. Each cell is either live (1) or dead (0). The state of the board evolves in generations based on the number of live neighbors (horizontal, vertical, and diagonal) each cell possesses. The rules governing life and death are standard: under-population and over-population kill live cells, while reproduction brings dead cells to life.

The critical challenge in LeetCode 289 is the requirement for simultaneous updates. The state of a cell in the next generation depends on the current state of its neighbors. If we update a cell's value immediately, its neighbors will effectively "see" the future state when calculating their own transitions, violating the rules.

Brute Force Approach for Game of Life

The most intuitive way to handle the simultaneous update requirement is to create a complete copy of the board. We read the neighbor counts from the original board and write the resulting state into the new copy. Once all cells are processed, we copy the new values back into the original board.

Pseudo-code:

text

function gameOfLife(board):
    copyBoard = deep_copy(board)
    for r from 0 to rows:
        for c from 0 to cols:
            neighbors = countNeighbors(copyBoard, r, c)
            if rules say live:
                board[r][c] = 1
            else:
                board[r][c] = 0

Complexity Analysis:

Time Complexity: $O(m \times n)$ , where $m$ is the number of rows and $n$ is the number of columns. We iterate through the grid once.
Space Complexity: $O(m \times n)$ to store the copyBoard.

Why it is suboptimal: While correct, this approach fails the "Follow up" constraint of solving the problem in-place. In a technical interview, allocating $O(m \times n)$ extra space is often considered a brute force solution when an $O(1)$ space solution exists. For very large matrices, doubling the memory usage is inefficient.

Algorithm Strategy: Array/Matrix Manipulation

The algorithm utilizes a two-pass strategy on the board matrix.

State Definition: We define four states to handle transitions:
- 0: Dead $\to$ Dead (No change)
- 1: Live $\to$ Live (No change)
- 2: Live $\to$ Dead (Under/Over-population)
- 3: Dead $\to$ Live (Reproduction)
First Pass (Determine Transitions):
- Iterate through every cell (row, col) in the matrix.
- For each cell, count its live neighbors. Crucially, when checking a neighbor's value, we must check if it was originally live. Based on our definitions, a cell was originally live if its value is 1 or 2.
- Apply the Game of Life rules:
  - If current is 1 and neighbors < 2 or > 3: Change state to 2.
  - If current is 0 and neighbors == 3: Change state to 3.
- Leave 0 and 1 unchanged if they don't transition.
Second Pass (Finalize):
- Iterate through the matrix again.
- Convert the composite states back to the standard binary representation:
  - 2 becomes 0.
  - 3 becomes 1.
- This can be achieved mathematically using the modulo operator: cell % 2 correctly maps 2 \to 0 and 3 \to 1, while preserving 0 and 1.

Execution Flow

Initialize: Determine board dimensions m and n. Define the 8 directional deltas for neighbor traversal.
Transition Pass:
- Loop r from 0 to m-1.
- Loop c from 0 to n-1.
- Initialize liveNeighbors = 0.
- Check all 8 neighbors. For a neighbor at (nr, nc), check if board[nr][nc] represents a live cell.
  - A cell is live if board[nr][nc] == 1 OR board[nr][nc] == 2.
- Apply Rules:
  - Rule 1 & 3 (Die): If board[r][c] == 1 and (liveNeighbors < 2 OR liveNeighbors > 3), set board[r][c] = 2.
  - Rule 4 (Reproduction): If board[r][c] == 0 and liveNeighbors == 3, set board[r][c] = 3.
Finalization Pass:
- Loop r from 0 to m-1.
- Loop c from 0 to n-1.
- Update board[r][c] = board[r][c] % 2.
- This effectively resolves 2 (was live, now dead) to 0, and 3 (was dead, now live) to 1.

Proof of Correctness

The correctness relies on the invariant that for any cell (r, c), the decision to transition is based strictly on the initial state of its neighbors.

By using state 2 (Live $\to$ Dead), we preserve the fact that the cell was live. When a neighbor at (r+1, c) calculates its count later, it sees 2, recognizes it as "originally live," and increments its count correctly.
By using state 3 (Dead $\to$ Live), we preserve the fact that the cell was dead. A neighbor sees 3, recognizes it as "originally dead," and does not increment its count.
The second pass resolves these temporary states to the final requirement, ensuring the output matches the simulation rules exactly.

Pattern Reuse Notes

The In-place Marking pattern used in this LeetCode 289 solution is versatile and appears in other popular interview questions:

LeetCode 73: Set Matrix Zeroes: Uses the first row and first column as markers to store which rows/cols should be zeroed out, avoiding $O(mn)$ space.
LeetCode 498: Diagonal Traverse: While primarily about traversal, complex variants often require marking visited cells in-place to prevent cycles or redundant processing without extra memory.

Feynman coach · Before you peek at the code

Can you explain the core insight in your own words?

If you can explain it before reading code, you’re far more likely to recall it under interview pressure.

Loading your attempt…

Reference Implementation

C++ Solution for LeetCode 289

cpp

1class Solution {
2public:
3    void gameOfLife(vector<vector<int>>& board) {
4        int m = board.size();
5        int n = board[0].size();
6        
7        // Directions for 8 neighbors
8        int dr[] = {-1, -1, -1, 0, 0, 1, 1, 1};
9        int dc[] = {-1, 0, 1, -1, 1, -1, 0, 1};
10        
11        // Pass 1: Mark transitions
12        // 0: Dead -> Dead
13        // 1: Live -> Live
14        // 2: Live -> Dead
15        // 3: Dead -> Live
16        for (int r = 0; r < m; ++r) {
17            for (int c = 0; c < n; ++c) {
18                int liveNeighbors = 0;
19                
20                for (int i = 0; i < 8; ++i) {
21                    int nr = r + dr[i];
22                    int nc = c + dc[i];
23                    
24                    if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
25                        // Check if neighbor was originally live (1 or 2)
26                        if (board[nr][nc] == 1 || board[nr][nc] == 2) {
27                            liveNeighbors++;
28                        }
29                    }
30                }
31                
32                // Apply rules
33                if (board[r][c] == 1) {
34                    if (liveNeighbors < 2 || liveNeighbors > 3) {
35                        board[r][c] = 2; // Live -> Dead
36                    }
37                } else { // board[r][c] == 0
38                    if (liveNeighbors == 3) {
39                        board[r][c] = 3; // Dead -> Live
40                    }
41                }
42            }
43        }
44        
45        // Pass 2: Finalize states
46        for (int r = 0; r < m; ++r) {
47            for (int c = 0; c < n; ++c) {
48                board[r][c] %= 2;
49            }
50        }
51    }
52};

Java Solution for LeetCode 289

java

1class Solution {
2    public void gameOfLife(int[][] board) {
3        int m = board.length;
4        int n = board[0].length;
5        
6        // Directions array for neighbor checking
7        int[] dr = {-1, -1, -1, 0, 0, 1, 1, 1};
8        int[] dc = {-1, 0, 1, -1, 1, -1, 0, 1};
9        
10        // Pass 1: Encode next state
11        // 0: Dead -> Dead
12        // 1: Live -> Live
13        // 2: Live -> Dead
14        // 3: Dead -> Live
15        for (int r = 0; r < m; r++) {
16            for (int c = 0; c < n; c++) {
17                int liveNeighbors = 0;
18                
19                for (int i = 0; i < 8; i++) {
20                    int nr = r + dr[i];
21                    int nc = c + dc[i];
22                    
23                    if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
24                        // Was the neighbor originally live? (1 or 2)
25                        if (board[nr][nc] == 1 || board[nr][nc] == 2) {
26                            liveNeighbors++;
27                        }
28                    }
29                }
30                
31                if (board[r][c] == 1) {
32                    // Rule 1 & 3: Live cell dies
33                    if (liveNeighbors < 2 || liveNeighbors > 3) {
34                        board[r][c] = 2;
35                    }
36                } else {
37                    // Rule 4: Dead cell becomes live
38                    if (liveNeighbors == 3) {
39                        board[r][c] = 3;
40                    }
41                }
42            }
43        }
44        
45        // Pass 2: Decode final state
46        for (int r = 0; r < m; r++) {
47            for (int c = 0; c < n; c++) {
48                board[r][c] %= 2;
49            }
50        }
51    }
52}

Python Solution for LeetCode 289

python

1class Solution:
2    def gameOfLife(self, board: List[List[int]]) -> None:
3        """
4        Do not return anything, modify board in-place instead.
5        """
6        m = len(board)
7        n = len(board[0])
8        
9        # Directions: (row_delta, col_delta)
10        directions = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]
11        
12        # Pass 1: Calculate next states and mark transitions
13        # 0: Dead -> Dead
14        # 1: Live -> Live
15        # 2: Live -> Dead
16        # 3: Dead -> Live
17        for r in range(m):
18            for c in range(n):
19                live_neighbors = 0
20                for dr, dc in directions:
21                    nr, nc = r + dr, c + dc
22                    if 0 <= nr < m and 0 <= nc < n:
23                        # Check if neighbor was originally live
24                        if board[nr][nc] == 1 or board[nr][nc] == 2:
25                            live_neighbors += 1
26                
27                # Apply rules
28                if board[r][c] == 1:
29                    if live_neighbors < 2 or live_neighbors > 3:
30                        board[r][c] = 2  # Live -> Dead
31                else:
32                    if live_neighbors == 3:
33                        board[r][c] = 3  # Dead -> Live
34        
35        # Pass 2: Update to final state
36        for r in range(m):
37            for c in range(n):
38                board[r][c] %= 2

AI Coach Insight

For Game of Life, focus on explaining why the structure works, not just naming Array/Matrix Manipulation Patterns.

Complexity Analysis

Time Complexity: $O(m \times n)$ $O (m \times n)$
- We iterate through the grid exactly twice. In the first pass, for each cell, we perform a constant number of operations (checking 8 neighbors). The second pass is also linear. Thus, the time is proportional to the number of cells.
Space Complexity: $O(1)$ $O (1)$
- We modify the input board in-place. We do not use any auxiliary data structures proportional to the input size.

Related Patterns

Pattern: Array/Matrix Manipulation Patterns
Subpattern: Array/Matrix - Set Matrix Zeroes (In-place Marking)

This problem fits the In-place Marking subpattern because we are modifying a matrix based on its initial state, and we need to preserve information about the initial state while simultaneously recording the new state. Just as in "Set Matrix Zeroes," where we use specific rows or columns to store flags, here we can use the cells themselves to store "intermediate" states.

Common Mistakes & FAQ

Why does my solution fail simultaneous updates?
- Mistake: Updating board[i][j] directly to 0 or 1 during the first pass.
- Reasoning: When you update cell (0,0) to a new value, the calculation for cell (0,1) will use this new value instead of the old value, corrupting the logic.
- Consequence: Incorrect output due to cascading state changes.
Why is my space complexity O(M*N)?
- Mistake: Creating a new_board or copy variable to store results.
- Reasoning: While this solves the simultaneity problem, it violates the constraint of solving it in-place.
- Consequence: Inefficient memory usage, potentially failing interview constraints.
Why am I getting Index Out of Bounds errors?
- Mistake: Iterating neighbors without checking boundary conditions (nr >= 0, nr < m, etc.).
- Reasoning: Grid neighbors (e.g., (-1, -1)) do not exist for corner or edge cells.
- Consequence: Runtime Exception.
Why is the output partially correct but slightly off?
- Mistake: Incorrectly checking the "original" state in the neighbor loop. For example, checking if board[nr][nc] == 1 only, ignoring the 2 state.
- Reasoning: Cells marked 2 are currently live but marked for death. They must be counted as live neighbors.
- Consequence: Logic errors specifically around dying cells.

Practise Game of Life and the problems around it

Game of Life is a Array/Matrix Manipulation Patterns problem, in the Set Matrix Zeroes (In-place Marking) subpattern. Once the approach above makes sense, write it yourself and then work through the neighbouring problems that reuse it.

Core insight

Game of Life · Array/Matrix Manipulation Patterns

Core Insight for Game of Life

Visual Description: Imagine the grid as a state machine. Instead of flipping a 1 directly to a 0, we flip it to a temporary marker, let's say 2.

If a cell holds 2, it tells us: "I am currently live (1) for calculation purposes, but I will be dead (0) in the next frame."
If a cell holds 3, it tells us: "I am currently dead (0) for calculation purposes, but I will be live (1) in the next frame."

By reading the "past" part of the code during neighbor counting and writing the "future" part of the code during the update, we simulate simultaneity in-place.

Deep dive

Full breakdown

Full reasoning, pitfalls, and implementation flow

LeetCode 289: Game of Life Solution & Explanation

Problem Overview

TL;DR: The optimal solution uses in-place marking with temporary state codes to simulate simultaneous updates without allocating extra memory for a board copy.

Brute Force Approach for Game of Life

Pseudo-code:

text

function gameOfLife(board):
    copyBoard = deep_copy(board)
    for r from 0 to rows:
        for c from 0 to cols:
            neighbors = countNeighbors(copyBoard, r, c)
            if rules say live:
                board[r][c] = 1
            else:
                board[r][c] = 0

Complexity Analysis:

Time Complexity: $O(m \times n)$ , where $m$ is the number of rows and $n$ is the number of columns. We iterate through the grid once.
Space Complexity: $O(m \times n)$ to store the copyBoard.

Algorithm Strategy: Array/Matrix Manipulation

The algorithm utilizes a two-pass strategy on the board matrix.

State Definition: We define four states to handle transitions:
- 0: Dead $\to$ Dead (No change)
- 1: Live $\to$ Live (No change)
- 2: Live $\to$ Dead (Under/Over-population)
- 3: Dead $\to$ Live (Reproduction)
First Pass (Determine Transitions):
- Iterate through every cell (row, col) in the matrix.
- For each cell, count its live neighbors. Crucially, when checking a neighbor's value, we must check if it was originally live. Based on our definitions, a cell was originally live if its value is 1 or 2.
- Apply the Game of Life rules:
  - If current is 1 and neighbors < 2 or > 3: Change state to 2.
  - If current is 0 and neighbors == 3: Change state to 3.
- Leave 0 and 1 unchanged if they don't transition.
Second Pass (Finalize):
- Iterate through the matrix again.
- Convert the composite states back to the standard binary representation:
  - 2 becomes 0.
  - 3 becomes 1.
- This can be achieved mathematically using the modulo operator: cell % 2 correctly maps 2 \to 0 and 3 \to 1, while preserving 0 and 1.

Execution Flow

Initialize: Determine board dimensions m and n. Define the 8 directional deltas for neighbor traversal.
Transition Pass:
- Loop r from 0 to m-1.
- Loop c from 0 to n-1.
- Initialize liveNeighbors = 0.
- Check all 8 neighbors. For a neighbor at (nr, nc), check if board[nr][nc] represents a live cell.
  - A cell is live if board[nr][nc] == 1 OR board[nr][nc] == 2.
- Apply Rules:
  - Rule 1 & 3 (Die): If board[r][c] == 1 and (liveNeighbors < 2 OR liveNeighbors > 3), set board[r][c] = 2.
  - Rule 4 (Reproduction): If board[r][c] == 0 and liveNeighbors == 3, set board[r][c] = 3.
Finalization Pass:
- Loop r from 0 to m-1.
- Loop c from 0 to n-1.
- Update board[r][c] = board[r][c] % 2.
- This effectively resolves 2 (was live, now dead) to 0, and 3 (was dead, now live) to 1.

Proof of Correctness

The correctness relies on the invariant that for any cell (r, c), the decision to transition is based strictly on the initial state of its neighbors.

By using state 2 (Live $\to$ Dead), we preserve the fact that the cell was live. When a neighbor at (r+1, c) calculates its count later, it sees 2, recognizes it as "originally live," and increments its count correctly.
By using state 3 (Dead $\to$ Live), we preserve the fact that the cell was dead. A neighbor sees 3, recognizes it as "originally dead," and does not increment its count.
The second pass resolves these temporary states to the final requirement, ensuring the output matches the simulation rules exactly.

Pattern Reuse Notes

The In-place Marking pattern used in this LeetCode 289 solution is versatile and appears in other popular interview questions:

LeetCode 73: Set Matrix Zeroes: Uses the first row and first column as markers to store which rows/cols should be zeroed out, avoiding $O(mn)$ space.
LeetCode 498: Diagonal Traverse: While primarily about traversal, complex variants often require marking visited cells in-place to prevent cycles or redundant processing without extra memory.

Feynman coach · Before you peek at the code

Can you explain the core insight in your own words?

If you can explain it before reading code, you’re far more likely to recall it under interview pressure.

Loading your attempt…

Reference Implementation

C++ Solution for LeetCode 289

cpp

1class Solution {
2public:
3    void gameOfLife(vector<vector<int>>& board) {
4        int m = board.size();
5        int n = board[0].size();
6        
7        // Directions for 8 neighbors
8        int dr[] = {-1, -1, -1, 0, 0, 1, 1, 1};
9        int dc[] = {-1, 0, 1, -1, 1, -1, 0, 1};
10        
11        // Pass 1: Mark transitions
12        // 0: Dead -> Dead
13        // 1: Live -> Live
14        // 2: Live -> Dead
15        // 3: Dead -> Live
16        for (int r = 0; r < m; ++r) {
17            for (int c = 0; c < n; ++c) {
18                int liveNeighbors = 0;
19                
20                for (int i = 0; i < 8; ++i) {
21                    int nr = r + dr[i];
22                    int nc = c + dc[i];
23                    
24                    if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
25                        // Check if neighbor was originally live (1 or 2)
26                        if (board[nr][nc] == 1 || board[nr][nc] == 2) {
27                            liveNeighbors++;
28                        }
29                    }
30                }
31                
32                // Apply rules
33                if (board[r][c] == 1) {
34                    if (liveNeighbors < 2 || liveNeighbors > 3) {
35                        board[r][c] = 2; // Live -> Dead
36                    }
37                } else { // board[r][c] == 0
38                    if (liveNeighbors == 3) {
39                        board[r][c] = 3; // Dead -> Live
40                    }
41                }
42            }
43        }
44        
45        // Pass 2: Finalize states
46        for (int r = 0; r < m; ++r) {
47            for (int c = 0; c < n; ++c) {
48                board[r][c] %= 2;
49            }
50        }
51    }
52};

Java Solution for LeetCode 289

java

1class Solution {
2    public void gameOfLife(int[][] board) {
3        int m = board.length;
4        int n = board[0].length;
5        
6        // Directions array for neighbor checking
7        int[] dr = {-1, -1, -1, 0, 0, 1, 1, 1};
8        int[] dc = {-1, 0, 1, -1, 1, -1, 0, 1};
9        
10        // Pass 1: Encode next state
11        // 0: Dead -> Dead
12        // 1: Live -> Live
13        // 2: Live -> Dead
14        // 3: Dead -> Live
15        for (int r = 0; r < m; r++) {
16            for (int c = 0; c < n; c++) {
17                int liveNeighbors = 0;
18                
19                for (int i = 0; i < 8; i++) {
20                    int nr = r + dr[i];
21                    int nc = c + dc[i];
22                    
23                    if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
24                        // Was the neighbor originally live? (1 or 2)
25                        if (board[nr][nc] == 1 || board[nr][nc] == 2) {
26                            liveNeighbors++;
27                        }
28                    }
29                }
30                
31                if (board[r][c] == 1) {
32                    // Rule 1 & 3: Live cell dies
33                    if (liveNeighbors < 2 || liveNeighbors > 3) {
34                        board[r][c] = 2;
35                    }
36                } else {
37                    // Rule 4: Dead cell becomes live
38                    if (liveNeighbors == 3) {
39                        board[r][c] = 3;
40                    }
41                }
42            }
43        }
44        
45        // Pass 2: Decode final state
46        for (int r = 0; r < m; r++) {
47            for (int c = 0; c < n; c++) {
48                board[r][c] %= 2;
49            }
50        }
51    }
52}

Python Solution for LeetCode 289

python

1class Solution:
2    def gameOfLife(self, board: List[List[int]]) -> None:
3        """
4        Do not return anything, modify board in-place instead.
5        """
6        m = len(board)
7        n = len(board[0])
8        
9        # Directions: (row_delta, col_delta)
10        directions = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]
11        
12        # Pass 1: Calculate next states and mark transitions
13        # 0: Dead -> Dead
14        # 1: Live -> Live
15        # 2: Live -> Dead
16        # 3: Dead -> Live
17        for r in range(m):
18            for c in range(n):
19                live_neighbors = 0
20                for dr, dc in directions:
21                    nr, nc = r + dr, c + dc
22                    if 0 <= nr < m and 0 <= nc < n:
23                        # Check if neighbor was originally live
24                        if board[nr][nc] == 1 or board[nr][nc] == 2:
25                            live_neighbors += 1
26                
27                # Apply rules
28                if board[r][c] == 1:
29                    if live_neighbors < 2 or live_neighbors > 3:
30                        board[r][c] = 2  # Live -> Dead
31                else:
32                    if live_neighbors == 3:
33                        board[r][c] = 3  # Dead -> Live
34        
35        # Pass 2: Update to final state
36        for r in range(m):
37            for c in range(n):
38                board[r][c] %= 2

Game of Life

Core insight

Core Insight for Game of Life

Full breakdown

LeetCode 289: Game of Life Solution & Explanation

Problem Overview

Brute Force Approach for Game of Life

Algorithm Strategy: Array/Matrix Manipulation

Execution Flow

Proof of Correctness

Pattern Reuse Notes

Can you explain the core insight in your own words?

Reference Implementation

C++ Solution for LeetCode 289

Java Solution for LeetCode 289

Python Solution for LeetCode 289

Practise Game of Life and the problems around it

Related problems

Game of Life

Core insight

Core Insight for Game of Life

Full breakdown

LeetCode 289: Game of Life Solution & Explanation

Problem Overview

Brute Force Approach for Game of Life

Algorithm Strategy: Array/Matrix Manipulation

Execution Flow

Proof of Correctness

Pattern Reuse Notes

Can you explain the core insight in your own words?

Reference Implementation

C++ Solution for LeetCode 289

Java Solution for LeetCode 289

Python Solution for LeetCode 289

Practise Game of Life and the problems around it

Related problems