LeetCode 289 - Game of Life

The problem asks us to simulate one iteration of Conway's Game of Life on a two-dimensional grid. Each cell in the grid is either alive, represented by 1, or dead, represented by 0. Every cell changes state simultaneously according to the number of live neighbors surrounding it.

leetcodemediumarraymatrixsimulation

LeetCode Problem 289

Difficulty: 🟡 Medium
Topics: Array, Matrix, Simulation

Solution

Problem Understanding

The problem asks us to simulate one iteration of Conway's Game of Life on a two-dimensional grid. Each cell in the grid is either alive, represented by 1, or dead, represented by 0. Every cell changes state simultaneously according to the number of live neighbors surrounding it.

Each cell has up to eight neighbors, including horizontal, vertical, and diagonal adjacent cells. The next state of a cell depends entirely on how many neighboring cells are alive in the current generation.

The important detail is that all updates happen simultaneously. This means we cannot immediately overwrite a cell with its next value and then use that modified value while processing nearby cells. Every decision must be based on the original board state.

The input is an m x n matrix named board. The task is to modify this matrix in-place so that it becomes the next generation of the Game of Life. No return value is required.

The constraints are relatively small, with both dimensions at most 25. Even an O(m * n * 8) solution is easily fast enough because each cell only checks eight neighbors. The challenge is not raw performance, but correctly handling simultaneous updates while staying in-place.

Several edge cases are important:

  • Cells on the border or corners have fewer than eight neighbors, so bounds checking is required.
  • A single live cell should die due to underpopulation.
  • Dense clusters may trigger overpopulation deaths.
  • Dead cells with exactly three live neighbors must become alive.
  • Since updates are simultaneous, modifying the board too early can corrupt neighbor counts for later cells.

Approaches

Brute Force Approach

The simplest solution is to create a completely separate board representing the next generation.

For every cell in the original grid, we count the number of live neighbors by checking all eight directions. Using the Game of Life rules, we determine whether the cell should be alive or dead in the next generation and write that result into a new matrix.

After processing all cells, we copy the new matrix back into the original board.

This approach is easy to reason about because the original board never changes while neighbor counts are being computed. Every decision uses consistent information.

However, this solution requires additional O(m * n) memory for the secondary board. The follow-up specifically asks whether we can solve the problem in-place, so we need a better approach.

Optimal In-Place Approach

The key insight is that each cell only has two states, alive or dead, but we can temporarily encode transition states directly inside the board.

We use four possible values:

  • 0 means dead and stays dead
  • 1 means alive and stays alive
  • -1 means alive but will die
  • 2 means dead but will become alive

This works because we can still determine the original state of a cell during neighbor counting:

  • Original live cells are 1 or -1
  • Original dead cells are 0 or 2

By preserving original information inside the encoded value, we can safely update the board in-place without corrupting neighbor calculations.

After the first pass computes transitions, a second pass converts all positive values to 1 and all non-positive values to 0.

Approach Time Complexity Space Complexity Notes
Brute Force O(m * n) O(m * n) Uses a separate board for the next state
Optimal O(m * n) O(1) Encodes transitions directly in the original board

Algorithm Walkthrough

  1. Determine the dimensions of the board.

We store the number of rows and columns so we can iterate through every cell and perform boundary checks while examining neighbors. 2. Define the eight possible neighbor directions.

Each cell can interact with all adjacent cells horizontally, vertically, and diagonally. We store these direction offsets so neighbor traversal becomes clean and reusable. 3. Traverse every cell in the board.

For each position (row, col), we count how many neighboring cells were originally alive. 4. Count live neighbors carefully.

While checking neighbors, we must remember that some cells may already contain temporary transition values.

A neighbor is considered originally alive if its value is either:

  • 1, alive and staying alive
  • -1, alive but scheduled to die

This preserves correctness even after partial updates. 5. Apply Game of Life rules using transition markers.

If a currently live cell has fewer than two or more than three live neighbors, it dies, so we mark it as -1.

If a currently dead cell has exactly three live neighbors, it becomes alive, so we mark it as 2.

Otherwise, the cell keeps its current state. 6. Perform a second traversal to finalize values.

After every cell has been processed, we convert:

  • Positive values to 1
  • Zero or negative values to 0

This produces the final next-generation board.

Why it works

The correctness comes from preserving the original state information during the first traversal. Even though cells are being updated in-place, the encoded values allow us to distinguish whether a cell was originally alive or dead. Therefore, every neighbor count is computed from the original generation, satisfying the simultaneous update requirement.

Python Solution

from typing import List

class Solution:
    def gameOfLife(self, board: List[List[int]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        
        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 row in range(rows):
            for col in range(cols):

                live_neighbors = 0

                for dr, dc in directions:
                    nr = row + dr
                    nc = col + dc

                    if 0 <= nr < rows and 0 <= nc < cols:
                        if board[nr][nc] == 1 or board[nr][nc] == -1:
                            live_neighbors += 1

                # Live cell
                if board[row][col] == 1:
                    if live_neighbors < 2 or live_neighbors > 3:
                        board[row][col] = -1

                # Dead cell
                else:
                    if live_neighbors == 3:
                        board[row][col] = 2

        # Finalize the board
        for row in range(rows):
            for col in range(cols):
                if board[row][col] > 0:
                    board[row][col] = 1
                else:
                    board[row][col] = 0

The implementation begins by storing the board dimensions and defining all eight neighbor directions. This allows the algorithm to systematically inspect every adjacent cell.

During the first traversal, the algorithm counts live neighbors for each cell. The important detail is that both 1 and -1 are treated as originally alive. This ensures that even after a cell has been marked for death, neighboring cells still see its original state correctly.

The transition encoding enables true in-place updates. Instead of allocating another matrix, the algorithm temporarily stores state changes directly inside the board.

Finally, the second traversal converts all encoded states back into standard binary values. Any positive value becomes 1, and everything else becomes 0.

Go Solution

func gameOfLife(board [][]int) {
    rows := len(board)
    cols := len(board[0])

    directions := [][]int{
        {-1, -1}, {-1, 0}, {-1, 1},
        {0, -1},           {0, 1},
        {1, -1},  {1, 0},  {1, 1},
    }

    for row := 0; row < rows; row++ {
        for col := 0; col < cols; col++ {

            liveNeighbors := 0

            for _, dir := range directions {
                nr := row + dir[0]
                nc := col + dir[1]

                if nr >= 0 && nr < rows && nc >= 0 && nc < cols {
                    if board[nr][nc] == 1 || board[nr][nc] == -1 {
                        liveNeighbors++
                    }
                }
            }

            // Live cell
            if board[row][col] == 1 {
                if liveNeighbors < 2 || liveNeighbors > 3 {
                    board[row][col] = -1
                }
            } else {
                // Dead cell
                if liveNeighbors == 3 {
                    board[row][col] = 2
                }
            }
        }
    }

    // Finalize states
    for row := 0; row < rows; row++ {
        for col := 0; col < cols; col++ {
            if board[row][col] > 0 {
                board[row][col] = 1
            } else {
                board[row][col] = 0
            }
        }
    }
}

The Go implementation follows the same logic as the Python version. Since Go slices are reference types, modifying board directly updates the original matrix in-place.

Unlike Python, Go does not have dynamic tuple structures, so neighbor directions are represented as a slice of integer slices. Bounds checking is explicit and uses standard conditional comparisons.

There are no integer overflow concerns because all values remain within a very small range.

Worked Examples

Example 1

Input:

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

Initial board:

Row Values
0 [0,1,0]
1 [0,0,1]
2 [1,1,1]
3 [0,0,0]

Consider cell (0,1):

  • Current state: alive

  • Live neighbors:

  • (1,2)

  • (1,1)

  • (1,0)

  • Total live neighbors = 2

The cell survives.

Consider cell (0,0):

  • Current state: dead

  • Live neighbors:

  • (0,1)

  • Total live neighbors = 1

The cell remains dead.

Consider cell (1,0):

  • Current state: dead

  • Live neighbors:

  • (0,1)

  • (2,0)

  • (2,1)

  • Total live neighbors = 3

The cell becomes alive, so it is temporarily marked as 2.

After the first pass, transition markers appear throughout the board.

Intermediate encoded board:

[
  [0,1,0],
  [2,0,1],
  [-1,1,1],
  [0,2,0]
]

After finalization:

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

Example 2

Input:

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

Cell-by-cell analysis:

Cell Live Neighbors Result
(0,0) 2 stays alive
(0,1) 2 stays alive
(1,0) 2 stays alive
(1,1) 3 becomes alive

Intermediate encoded board:

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

Final board:

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

Complexity Analysis

Measure Complexity Explanation
Time O(m * n) Every cell checks at most eight neighbors
Space O(1) Updates are stored directly inside the board

The algorithm performs two passes over the board. During the first pass, each cell examines eight neighboring positions, which is constant work. Therefore, the total runtime grows linearly with the number of cells.

The space complexity is constant because no additional matrix proportional to the board size is allocated. Only a few variables and the fixed direction list are used.

Test Cases

from typing import List

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 row in range(rows):
            for col in range(cols):

                live_neighbors = 0

                for dr, dc in directions:
                    nr = row + dr
                    nc = col + dc

                    if 0 <= nr < rows and 0 <= nc < cols:
                        if board[nr][nc] in (1, -1):
                            live_neighbors += 1

                if board[row][col] == 1:
                    if live_neighbors < 2 or live_neighbors > 3:
                        board[row][col] = -1
                else:
                    if live_neighbors == 3:
                        board[row][col] = 2

        for row in range(rows):
            for col in range(cols):
                board[row][col] = 1 if board[row][col] > 0 else 0

solution = Solution()

# Example 1
board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
solution.gameOfLife(board)
assert board == [[0,0,0],[1,0,1],[0,1,1],[0,1,0]]  # standard example

# Example 2
board = [[1,1],[1,0]]
solution.gameOfLife(board)
assert board == [[1,1],[1,1]]  # reproduction case

# Single dead cell
board = [[0]]
solution.gameOfLife(board)
assert board == [[0]]  # remains dead

# Single live cell
board = [[1]]
solution.gameOfLife(board)
assert board == [[0]]  # dies from underpopulation

# Stable block pattern
board = [
    [1,1],
    [1,1]
]
solution.gameOfLife(board)
assert board == [
    [1,1],
    [1,1]
]  # stable structure

# Blinker oscillator
board = [
    [0,1,0],
    [0,1,0],
    [0,1,0]
]
solution.gameOfLife(board)
assert board == [
    [0,0,0],
    [1,1,1],
    [0,0,0]
]  # oscillator transition

# Overpopulation
board = [
    [1,1,1],
    [1,1,1],
    [1,1,1]
]
solution.gameOfLife(board)
assert board == [
    [1,0,1],
    [0,0,0],
    [1,0,1]
]  # dense population deaths
Test Why
Standard example Validates general rule interactions
Reproduction example Confirms dead cells become alive correctly
Single dead cell Smallest possible empty board
Single live cell Verifies underpopulation
Stable block pattern Ensures stable structures remain unchanged
Blinker oscillator Validates simultaneous updates
Overpopulation case Confirms overcrowded cells die

Edge Cases

A single live cell is an important edge case because it has zero live neighbors and must die from underpopulation. Naive implementations sometimes forget to handle isolated cells correctly. This implementation counts neighbors accurately and marks the cell as -1, which later becomes 0.

Border and corner cells are another common source of bugs because they do not have all eight neighbors. Without proper bounds checking, the algorithm may attempt invalid array access. The implementation explicitly checks that every neighbor coordinate remains within the board dimensions before accessing it.

Simultaneous updates are the most subtle edge case in the problem. If cells are updated immediately, later neighbor counts may use already-modified values instead of original states. The transition encoding technique solves this problem by preserving original state information throughout the first traversal.

Dense populations also require careful handling. A live cell with more than three neighbors must die from overpopulation. In tightly packed regions, many cells change simultaneously, making in-place correctness especially important. The encoded state system ensures every decision is still based on the original generation.