How do you solve Game of Life on LeetCode?

Game of Life (LeetCode #289) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n²) time complexity and O(1) space complexity. Key insight: Understanding the rules of the Game of Life is crucial for implementing the solution.

What is the brute force solution for Game of Life?

The brute force approach for Game of Life is Brute Force, with O(n²) time complexity and O(n²) space complexity. The brute force approach involves creating a copy of the board and applying the rules to each cell based on the original state. This is straightforward but inefficient as it requires multiple passes over the grid. The optimal Optimal Solution approach improves this to O(n²).

What algorithm or data structure is used to solve Game of Life?

Game of Life uses the following concepts: Array, Matrix, Simulation. The recommended patterns to study are: Array, Matrix, Simulation.

What are the interview tips for Game of Life?

Explain your thought process clearly, especially when transitioning from brute force to optimal. Discuss the trade-offs between space and time complexity. Practice dry runs on paper to solidify your understanding.

What are common mistakes when solving Game of Life?

Not considering edge cases like cells on the borders. Failing to update the board correctly when using temporary states.

#289

Game of Life

Medium

ArrayMatrixSimulationArrayMatrixSimulation

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n²)
Space	O(n²)	O(1)

💡

Intuition

Time O(n²)Space O(1)

The optimal solution modifies the board in place by using a two-state system. We can encode the next state of each cell using temporary values to avoid using extra space.

⚙️

Algorithm

3 steps

1Step 1: Iterate through each cell and count live neighbors, using temporary values to indicate the next state.
2Step 2: Update the board based on the counts, using 2 for live cells that will die and -1 for dead cells that will come to life.
3Step 3: Convert temporary values back to 0 and 1 to finalize the board.

solution.py22 lines

1# Full working Python code
2
3def gameOfLife(board):
4    directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
5    for i in range(len(board)):
6        for j in range(len(board[0])):
7            live_neighbors = 0
8            for d in directions:
9                ni, nj = i + d[0], j + d[1]
10                if 0 <= ni < len(board) and 0 <= nj < len(board[0]):
11                    if board[ni][nj] == 1 or board[ni][nj] == -1:
12                        live_neighbors += 1
13            if board[i][j] == 1 and (live_neighbors < 2 or live_neighbors > 3):
14                board[i][j] = -1  # Mark for death
15            if board[i][j] == 0 and live_neighbors == 3:
16                board[i][j] = 2  # Mark for birth
17    for i in range(len(board)):
18        for j in range(len(board[0])):
19            if board[i][j] == -1:
20                board[i][j] = 0
21            if board[i][j] == 2:
22                board[i][j] = 1

ℹ

Complexity note: The time complexity remains O(n²) as we still iterate through each cell, but the space complexity is reduced to O(1) since we modify the board in place without needing additional storage.

1Understanding the rules of the Game of Life is crucial for implementing the solution.
2In-place modifications can save space and improve efficiency.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.