Game of Life

Problem

You are given an m x n grid of cells, where each cell is either alive (1) or dead (0). Every cell interacts with its eight neighbors (horizontal, vertical, diagonal). The grid advances to its next generation by applying these rules to every cell simultaneously:

1. A live cell with fewer than two live neighbors dies (underpopulation).
2. A live cell with two or three live neighbors survives.
3. A live cell with more than three live neighbors dies (overpopulation).
4. A dead cell with exactly three live neighbors becomes alive (reproduction).

Update the board in place to its next state. Every cell’s next state must be computed from the current generation, so an already-updated cell must not influence its neighbors.

Follow-up: can you do it with O(1) extra space?

Examples

Example 1: board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]] → [[0,0,0],[1,0,1],[0,1,1],[0,1,0]] The isolated live cells at the top die of underpopulation, while dead cells with exactly three live neighbors become alive.

Example 2: board = [[1,1],[1,0]] → [[1,1],[1,1]] Each live cell has exactly two live neighbors and survives; the dead corner has three live neighbors and is born.

Constraints

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

The board is small, so any per-cell scan passes. The point of the exercise is the in-place / O(1)-space follow-up.

Think about it first

TL;DR

In-place state encoding (two-bits-in-one-int) — O(m·n) time, O(1) extra space.

Approach 1 — Brute force (copy the board)

Snapshot the whole board, then compute every cell’s next state by counting live neighbors in the snapshot while writing into the original. The snapshot preserves the current generation, so writes never corrupt neighbor counts.

from typing import List
import copy


def gameOfLife(board: List[List[int]]) -> None:
    m, n = len(board), len(board[0])
    snapshot = copy.deepcopy(board)

    def live_neighbors(r: int, c: int) -> int:
        count = 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 and snapshot[nr][nc] == 1:
                    count += 1
        return count

    for r in range(m):
        for c in range(n):
            alive = live_neighbors(r, c)
            if snapshot[r][c] == 1 and alive in (2, 3):
                board[r][c] = 1
            elif snapshot[r][c] == 0 and alive == 3:
                board[r][c] = 1
            else:
                board[r][c] = 0

Complexity: O(m·n) time, O(m·n) space for the copy. With m, n <= 25 this passes easily. It fails only the follow-up’s O(1)-space requirement, which is the point of the exercise.

Approach 2 — In-place state encoding

Each cell needs to remember only its old state and its new state. Instead of a second board, widen the value domain of a single int: keep 0 and 1 meaning “no change”, and add two transition markers:

• 2 = was live, will be dead
• 3 = was dead, will be live

During neighbor counting, a cell was live if its value is 1 or 2. A second pass then decodes: 2 -> 0, 3 -> 1.

flowchart LR
  L1["was live (1)"] -->|"survives"| D1["stays 1 -> 1"]
  L1 -->|"under/overpopulation"| D2["mark 2 -> 0"]
  D0["was dead (0)"] -->|"3 live neighbors"| D3["mark 3 -> 1"]
  D0 -->|"otherwise"| D4["stays 0 -> 0"]

from typing import List


def gameOfLife(board: List[List[int]]) -> None:
    m, n = len(board), len(board[0])

    def was_live(r: int, c: int) -> bool:
        return 0 <= r < m and 0 <= c < n and board[r][c] in (1, 2)

    for r in range(m):
        for c in range(n):
            alive = 0
            for dr in (-1, 0, 1):
                for dc in (-1, 0, 1):
                    if (dr or dc) and was_live(r + dr, c + dc):
                        alive += 1
            if board[r][c] == 1 and alive not in (2, 3):
                board[r][c] = 2      # live -> dead
            elif board[r][c] == 0 and alive == 3:
                board[r][c] = 3      # dead -> live

    for r in range(m):
        for c in range(n):
            board[r][c] = 1 if board[r][c] in (1, 3) else 0

Walkthrough on Example 2, board = [[1,1],[1,0]]:

1. Cell (0,0): neighbors (0,1)=1, (1,0)=1, (1,1)=0 → 2 live. Live with 2 → survives, stays 1.
2. Cell (0,1): neighbors (0,0), (1,0) live → 2 live → stays 1.
3. Cell (1,0): neighbors (0,0), (0,1) live → 2 live → stays 1.
4. Cell (1,1): value 0; neighbors (0,0), (0,1), (1,0) all read as “was live” (values 1) → 3 live → marked 3 (dead → live).
5. Decode pass: 3 becomes 1. Final board [[1,1],[1,1]].

Step 4 shows why the marker scheme keeps the count correct: had cell (0,0) died, it would hold 2, and was_live would still count it as a live neighbor of (1,1).

Complexity: O(m·n) time, O(1) extra space.

Common pitfalls

• Updating cells directly as you scan — later cells then count next-generation neighbors, corrupting the simultaneity rule.
• Counting the cell itself as its own neighbor (forgetting to skip dr == dc == 0).
• Decoding with board[r][c] %= 2 — that maps 2 -> 0 and 3 -> 1 correctly, but only if you chose the encoding that way; with ad-hoc markers like -1, double-check the decode table.
• Off-by-one on the border: neighbor coordinates must be bounds-checked in both dimensions.

Pattern takeaway

When an in-place transformation needs both the old and new value of each slot, enlarge the value domain so one slot encodes both states, then decode in a final pass instead of allocating a second array. The same technique (sentinel values or spare bits) reappears in in-place matrix problems such as Set Matrix Zeroes and Rotate Image variants.