LeetCode 289: Game of Life

Problem Restatement

We are given an m x n board.

Each cell is either:

Each cell has up to eight neighbors:

horizontal
vertical
diagonal

The next board state is computed using these rules:

All cells must update simultaneously.

That means when deciding the next state of one cell, we must use the original state of its neighbors, not already-updated values.

The official statement asks us to update the board in-place. The follow-up emphasizes that simultaneous updates make direct mutation tricky. The listed constraints include 1 <= m, n <= 25 and board[i][j] is either 0 or 1.

Input and Output

Function shape:

class Solution:
    def gameOfLife(self, board: list[list[int]]) -> None:
        ...

Examples

For:

board = [
    [0, 1, 0],
    [0, 0, 1],
    [1, 1, 1],
    [0, 0, 0],
]

The next state is:

[
    [0, 0, 0],
    [1, 0, 1],
    [0, 1, 1],
    [0, 1, 0],
]

For:

board = [
    [1, 1],
    [1, 0],
]

The next state is:

[
    [1, 1],
    [1, 1],
]

The dead cell in the bottom-right corner has exactly three live neighbors, so it becomes live.

First Thought: Use a Copy

The easiest correct method is to copy the original board first.

Then we read from the copy and write into the original board.

class Solution:
    def gameOfLife(self, board: list[list[int]]) -> None:
        rows = len(board)
        cols = len(board[0])

        original = [row[:] for row in board]

        directions = [
            (-1, -1), (-1, 0), (-1, 1),
            (0, -1),           (0, 1),
            (1, -1),  (1, 0),  (1, 1),
        ]

        for r in range(rows):
            for c in range(cols):
                live = 0

                for dr, dc in directions:
                    nr = r + dr
                    nc = c + dc

                    if 0 <= nr < rows and 0 <= nc < cols:
                        if original[nr][nc] == 1:
                            live += 1

                if original[r][c] == 1:
                    if live < 2 or live > 3:
                        board[r][c] = 0
                else:
                    if live == 3:
                        board[r][c] = 1

This is simple and correct.

Problem With the Copy Solution

The copy solution uses extra space proportional to the whole board.

For an m x n board, that is:

O(m * n)

The follow-up asks for an in-place solution.

The challenge is that if we directly change a cell from 1 to 0, later cells may count it as dead, even though it was originally live.

We need to store both:

1. The old state.
2. The next state.

inside the same cell.

Key Insight

Use temporary encoded states.

We need to distinguish four cases:

The important trick is neighbor counting.

When counting live neighbors, a cell should count as originally live if its old state was 1.

That means both of these should count as live:

1
2

because 2 means the cell was live but will die.

These should count as originally dead:

0
-1

because -1 means the cell was dead but will become live.

So a neighbor is originally live when:

board[nr][nc] > 0

After marking every cell, we do a second pass to convert temporary states into final states.

Algorithm

Use two passes.

First pass:

For each cell:

1. Count originally live neighbors.
2. If the current cell is live:
   • It dies if live neighbors are fewer than 2 or greater than 3.
   • Mark it as 2.
3. If the current cell is dead:
   • It becomes live if live neighbors equal 3.
   • Mark it as -1.

Second pass:

Convert temporary states:

Correctness

During the first pass, every cell still exposes its original state through its sign.

A value greater than 0 means the cell was originally live. A value less than or equal to 0 means the cell was originally dead.

Therefore, even after some cells have been marked with temporary values, neighbor counting still uses the original board state.

For each cell, the algorithm counts exactly the number of originally live neighbors among the eight surrounding cells.

Then it applies the Game of Life rules:

• A live cell with fewer than two live neighbors is marked to die.
• A live cell with two or three live neighbors remains live.
• A live cell with more than three live neighbors is marked to die.
• A dead cell with exactly three live neighbors is marked to become live.

So after the first pass, every cell contains both enough information about its original state and its correct next state.

The second pass replaces each encoded value with its final state.

Therefore, after the second pass, the board equals the simultaneous next state required by the problem.

Complexity

Let:

R = number of rows
C = number of columns

The factor 8 is constant, so the time complexity is linear in the number of cells.

Implementation

class Solution:
    def gameOfLife(self, board: list[list[int]]) -> None:
        rows = len(board)
        cols = len(board[0])

        directions = [
            (-1, -1), (-1, 0), (-1, 1),
            (0, -1),           (0, 1),
            (1, -1),  (1, 0),  (1, 1),
        ]

        for r in range(rows):
            for c in range(cols):
                live = 0

                for dr, dc in directions:
                    nr = r + dr
                    nc = c + dc

                    if nr < 0 or nr >= rows:
                        continue

                    if nc < 0 or nc >= cols:
                        continue

                    if board[nr][nc] > 0:
                        live += 1

                if board[r][c] == 1:
                    if live < 2 or live > 3:
                        board[r][c] = 2

                elif board[r][c] == 0:
                    if live == 3:
                        board[r][c] = -1

        for r in range(rows):
            for c in range(cols):
                if board[r][c] == 2:
                    board[r][c] = 0
                elif board[r][c] == -1:
                    board[r][c] = 1

Code Explanation

We first get the board size:

rows = len(board)
cols = len(board[0])

Then we list the eight neighbor directions:

directions = [
    (-1, -1), (-1, 0), (-1, 1),
    (0, -1),           (0, 1),
    (1, -1),  (1, 0),  (1, 1),
]

For each cell, we count originally live neighbors:

if board[nr][nc] > 0:
    live += 1

This counts both 1 and 2 as originally live.

If the current cell is live and should die:

if board[r][c] == 1:
    if live < 2 or live > 3:
        board[r][c] = 2

we mark it as 2.

If the current cell is dead and should become live:

elif board[r][c] == 0:
    if live == 3:
        board[r][c] = -1

we mark it as -1.

The second pass turns temporary states into final states:

if board[r][c] == 2:
    board[r][c] = 0
elif board[r][c] == -1:
    board[r][c] = 1

Cells already equal to 0 or 1 stay unchanged.

Testing

def test_game_of_life():
    s = Solution()

    board = [
        [0, 1, 0],
        [0, 0, 1],
        [1, 1, 1],
        [0, 0, 0],
    ]

    s.gameOfLife(board)

    assert board == [
        [0, 0, 0],
        [1, 0, 1],
        [0, 1, 1],
        [0, 1, 0],
    ]

    board = [
        [1, 1],
        [1, 0],
    ]

    s.gameOfLife(board)

    assert board == [
        [1, 1],
        [1, 1],
    ]

    board = [[1]]
    s.gameOfLife(board)
    assert board == [[0]]

    board = [[0]]
    s.gameOfLife(board)
    assert board == [[0]]

    print("all tests passed")

test_game_of_life()

Test meaning: