#289

Medium

LeetCode Problem Workspace

Game of Life

Solve the Game of Life by updating each cell based on its eight neighbors using Array and Matrix simulation patterns efficiently.

array matrix simulation

Problem Statement

The Game of Life is a cellular automaton invented by John Horton Conway in 1970. You are given an m x n grid where each cell is either live (1) or dead (0). Each cell interacts with its eight neighbors horizontally, vertically, and diagonally, following rules that determine whether it survives, dies, or becomes alive in the next state.

Your task is to compute the next state of the entire grid simultaneously, applying the rules to every cell without changing intermediate values. Births and deaths occur simultaneously, so careful handling of updates is required to avoid premature state changes and ensure correctness across the matrix.

Examples

Example 1

Input: board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]

Output: [[0,0,0],[1,0,1],[0,1,1],[0,1,0]]

Example details omitted.

Example 2

Input: board = [[1,1],[1,0]]

Output: [[1,1],[1,1]]

Example details omitted.

Constraints

m == board.length
n == board[i].length
1 <= m, n <= 25
board[i][j] is 0 or 1.

Solution Approach

Count live neighbors efficiently

Traverse each cell and count its live neighbors by checking all eight directions. Use nested loops with bounds checking to avoid index errors while maintaining the matrix structure.

Use in-place state encoding

Mark cells with temporary values to indicate transitions (e.g., 2 for live-to-dead, 3 for dead-to-live). This preserves the original state while allowing simultaneous updates in one pass over the board.

Finalize board updates

After marking all transitions, traverse the board again to convert temporary markers to final states (1 for live, 0 for dead). This two-pass method ensures simultaneous application of Game of Life rules across the matrix.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(m n) for both passes over the board, as each cell is visited a constant number of times to check neighbors. Space complexity can be O(1) if using in-place encoding, or O(m n) if creating a separate matrix for the next state.

What Interviewers Usually Probe

Are you handling neighbor counts without modifying the board prematurely?
Can you optimize the solution to avoid extra space while maintaining simultaneous updates?
Do you understand why marking states in-place prevents incorrect state transitions?

Common Pitfalls or Variants

Common pitfalls

Updating cells in a single pass without markers causes neighbor counts to be incorrect.
Forgetting to check all eight neighbors, leading to off-by-one errors on edges.
Using extra space unnecessarily when in-place marking is possible.

Follow-up variants

Implement the Game of Life on an infinite grid where new cells can appear dynamically.
Compute k steps of the Game of Life efficiently without recomputing the entire board each time.
Optimize neighbor checks using prefix sums or bit manipulation for larger matrices.

FAQ

What is the main challenge in solving the Game of Life?

The key challenge is updating all cells simultaneously without corrupting neighbor information, which requires careful state handling.

Can I solve Game of Life without extra space?

Yes, by using in-place markers to indicate transitional states, you can compute the next board state without additional arrays.

How do I count neighbors efficiently in a matrix?

Check all eight directions for each cell using loops with bounds checking to prevent index errors, ensuring accurate live neighbor counts.

What are common mistakes in this Array plus Matrix pattern?

Prematurely updating cells, missing diagonal neighbors, or mismanaging temporary markers are frequent pitfalls in Game of Life implementations.

Is there a way to simulate multiple steps of Game of Life efficiently?

Yes, by iteratively applying the in-place update strategy or using memoization techniques for repeated patterns, you can simulate multiple steps efficiently.

terminal

Solution

Solution 1: In-place marking

Let's define two new states. State $2$ indicates that the living cell becomes dead in the next state, and state $-1$ indicates that the dead cell becomes alive in the next state. Therefore, for the current grid we are traversing, if the grid is greater than $0$, it means that the current grid is a living cell, otherwise it is a dead cell.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def gameOfLife(self, board: List[List[int]]) -> None:
        m, n = len(board), len(board[0])
        for i in range(m):
            for j in range(n):
                live = -board[i][j]
                for x in range(i - 1, i + 2):
                    for y in range(j - 1, j + 2):
                        if 0 <= x < m and 0 <= y < n and board[x][y] > 0:
                            live += 1
                if board[i][j] and (live < 2 or live > 3):
                    board[i][j] = 2
                if board[i][j] == 0 and live == 3:
                    board[i][j] = -1
        for i in range(m):
            for j in range(n):
                if board[i][j] == 2:
                    board[i][j] = 0
                elif board[i][j] == -1:
                    board[i][j] = 1

Continue Practicing

#498 diagonal traverse #59 spiral matrix ii #54 spiral matrix