Skip to content

289. Game of Life

On LeetCode ->

Problem

Update a binary grid in place by applying Conway's Game of Life simultaneously to every cell using its eight neighbors.

  1. Any live cell with fewer than two live neighbors dies as if caused by under-population.
  2. Any live cell with two or three live neighbors lives on to the next generation.
  3. Any live cell with more than three live neighbors dies, as if by over-population.
  4. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
[[0,1,0],       [[0,0,0],
 [0,0,1],   ->   [1,0,1],
 [1,1,1],        [0,1,1],
 [0,0,0]]        [0,1,0]]

Key trick

Store both generations in each integer: bit 0 keeps the original state, while bit 1 records the next state; after processing all cells, shift bit 1 into place.

Trap

  • Updating cells without preserving their original state breaks simultaneous evaluation.
  • Count all eight neighbors before applying the rules.
  • Transitional values must be read through their original-state bit.

Why is it interesting?

It turns an apparently \(O(mn)\)-space simulation into an in-place update through compact state encoding.

Python solution

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

        for r in range(m):
            for c in range(n):
                live = 0

                for dr in (-1, 0, 1):
                    for dc in (-1, 0, 1):
                        if dr == 0 and dc == 0:
                            continue

                        nr, nc = r + dr, c + dc
                        if 0 <= nr < m and 0 <= nc < n:
                            # Bit 0 always contains the original state.
                            live += board[nr][nc] & 1

                cell = board[r][c] & 1

                # Bit 1 stores the next state without changing bit 0.
                if live == 3 or (cell == 1 and live == 2):
                    board[r][c] |= 2

        for r in range(m):
            for c in range(n):
                # Discard the original state and expose the next state.
                board[r][c] >>= 1

Time complexity: \(O(mn)\).

Auxiliary space complexity: \(O(1)\).

Comment on my solution

The auxiliary matrix approach is valid, but the implementation resets cnt_live_neighbor inside the neighbor loop and applies the rules before all neighbors have been counted. Consequently, the count never exceeds one.

# brute force with anex matrix that we copy back at the end

# WRONG
class Solution:
    def gameOfLife(self, board: list[list[int]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        # [[0,1,0],      [[0,0,0],
        #  [0,0,1],       [1,0,1],
        #  [1,1,1],   ->  [0,1,1],
        #  [0,0,0]]       [0,1,0]]
        # [[1,1],      [[1,1],
        #  [1,0]]   ->  [1,1]]

        m, n = len(board), len(board[0])
        nxt = [[0]*n for _ in range(m)]

        for r in range(m):
            for c in range(n):
                for dr, dc in ((-1,-1), (-1, 0), (-1, 1),
                               (0, 1), (1,1), (1, 0),
                               (1, -1), (0, -1)):
                    nr, nc = r + dr, c + dc
                    cnt_live_neighbor = 0
                    if 0 <= nr < m and 0 <= nc < n and board[nr][nc]:
                        cnt_live_neighbor += 1
                    cell = board[r][c]
                    if cell == 0:
                        if cnt_live_neighbor == 3:
                            nxt[r][c] = 1
                        else:
                            nxt[r][c] = 0
                        continue
                    if cnt_live_neighbor < 2:
                        nxt[r][c] = 0
                    elif 2 <= cnt_live_neighbor <= 3:
                        nxt[r][c] = 1
                    else:
                        nxt[r][c] = 0
        for r in range(m):
            for c in range(n):
                board[r][c] = nxt[r][c]