Game of Life (LeetCode 289)

The problem

You get an m × n board of cells, each 1 (live) or 0 (dead). Every cell has up to eight neighbours (including diagonals). Compute the next generation, where all cells update at the same moment based on the current board:

• a live cell with fewer than 2 or more than 3 live neighbours dies;
• a live cell with 2 or 3 live neighbours stays alive;
• a dead cell with exactly 3 live neighbours becomes live.

Update the board in place.

Input:      Output:
0 1 0       0 0 0
0 0 1       1 0 1
1 1 1       0 1 1
0 0 0       0 1 0

For example, (1, 0) is dead with exactly 3 live neighbours, so it comes to life; (0, 1) is live with only 1, so it dies.

How to think about it

Start with brute force. Copy the board. For each cell, count live neighbours in the copy and write the new value into the original. That is O(m·n) time and correct, but it needs O(m·n) extra space. The follow-up asks for O(1) extra space.

Why in place is hard. If you overwrite a cell with its new value as you scan, later neighbours count the new value instead of the old one. The rule says everything updates at once, so every count must see the old board.

The key insight: one cell can hold two bits of state. A cell only needs to remember “was I alive?” and “will I be alive?“. Use extra codes:

• 2 = was live, now dead;
• 3 = was dead, now live.

When counting neighbours, treat 1 and 2 as live (both were live in the old board). Codes 0 and 3 were dead. So the old state stays readable all the way through the scan. At the end, cell % 2 turns 0 and 2 into 0 (dead) and 1 and 3 into 1 (live), which is exactly the new board.

Which pattern is this? In-place matrix simulation with state encoding. The tell is “update a grid in place where each cell depends on its neighbours’ old values”. Encoding extra state in unused values (or spare bits) avoids the copy.

Approach

1. Write a helper live_neighbors(r, c) that counts the eight neighbours inside the board whose value is 1 or 2.
2. Scan every cell and count its live neighbours:
   • if it is 1 and the count is below 2 or above 3, set it to 2;
   • if it is 0 and the count is exactly 3, set it to 3.
3. Scan again and replace every cell with cell % 2.

Solution

def game_of_life(board):
    R, C = len(board), len(board[0])
    def live_neighbors(r, c):
        cnt = 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 < R and 0 <= nc < C and board[nr][nc] in (1, 2):  # 1, 2 were live
                    cnt += 1
        return cnt
    for r in range(R):
        for c in range(C):
            n = live_neighbors(r, c)
            if board[r][c] == 1 and (n < 2 or n > 3): board[r][c] = 2   # live -> dead
            if board[r][c] == 0 and n == 3:           board[r][c] = 3   # dead -> live
    for r in range(R):
        for c in range(C): board[r][c] %= 2          # keep only the new state
    return board
# game_of_life([[0,1,0],[0,0,1],[1,1,1],[0,0,0]]) -> [[0,0,0],[1,0,1],[0,1,1],[0,1,0]]

Dry run

On the example, showing only the cells whose code changes in the first pass:

After the first pass the board is [[0,2,0],[3,0,1],[2,1,1],[0,3,0]]. Note that (1, 0) still counts (0, 1) as live because 2 means “was live”. Taking mod 2 gives [[0,0,0],[1,0,1],[0,1,1],[0,1,0]].

Complexity

• Time: O(m·n). Each cell checks at most 8 neighbours, a constant, and there are two passes.
• Space: O(1) extra. The new state is stored inside the board itself.

Edge cases and pitfalls

• Counting 3 as live is the classic bug. A 3 was dead in the old board, so it must not count.
• Border cells have fewer than 8 neighbours; the bounds check handles it.
• 1 × 1 board: a single live cell has 0 neighbours and dies.
• Updating with 0/1 directly during the scan corrupts counts for cells that come later.
• Infinite board follow-up: store only live cells in a set of coordinates and count neighbours from there.

Related problems

• Set Matrix Zeroes (LeetCode 73): another in-place grid update that hides extra state inside the matrix.
• Number of Islands (LeetCode 200): grid neighbour scanning with bounds checks, and marking cells in place.
• Rotting Oranges (LeetCode 994): a grid that evolves in generations, where each step depends on the previous state.