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. “Simultaneously” is the catch: every cell’s next state must be computed from the current generation, so you cannot let an already-updated cell 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 lone live cells at the top die of underpopulation while dead cells adjacent to three live ones spring to life.

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 tiny, so any per-cell scan passes — the real constraint 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)

The naive move: snapshot the whole board, then compute every cell’s next state by counting live neighbors in the snapshot while writing into the original.

from typing import List
import copy


class Solution:
    def gameOfLife(self, 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 — what kills it is the follow-up’s O(1)-space requirement, which is the whole point of the exercise.

Approach 2 — In-place state encoding

The insight: each cell only needs to remember two bits of information — its old state and its new state. Instead of a second board, widen the alphabet 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

While counting neighbors, a cell was live iff its value is 1 or 2. After the first pass, a second pass decodes: 2 -> 0, 3 -> 1.

from typing import List


class Solution:
    def gameOfLife(self, 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]]. ✓

Note how in step 4 the marker scheme is what keeps the count honest: 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, don’t reach for a second array — enlarge the value domain so one slot encodes both states, then decode in a final pass. The same trick (sentinel values / spare bits) reappears in in-place matrix problems like Set Matrix Zeroes and Rotate Image variants.