Game of Life: In-Place State Encoding

LeetCode 289: Game of Life asks you to simulate one step of Conway's Game of Life on an m x n board, updating every cell simultaneously. The four rules are:

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

"Simultaneously" is the key word. Every cell's fate depends on the current generation, not the partially updated board. The naive fix is copying the entire board first. But can you do it in place with O(1) extra space? Yes, and the trick is state encoding.

Live cells shown filled

→

↓

3 = alive, stays alive. 2 = dead, becomes alive.

→

↓

Right-shift each cell to get the new state

The trick: state encoding

The board only uses values 0 (dead) and 1 (alive), but an integer can hold more than one bit of information. The idea: use bit 0 for the old state and bit 1 for the new state, all in the same cell.

Here is the encoding:

• 0 (binary 00): was dead, stays dead
• 1 (binary 01): was alive, will die (has not been marked to survive yet)
• 2 (binary 10): was dead, becomes alive
• 3 (binary 11): was alive, stays alive

Reading the old state during processing is simple: board[i][j] % 2 (or board[i][j] & 1). Since we only write to bit 1, the old state in bit 0 stays intact while we scan neighbors. After processing every cell, a single pass of board[i][j] >>= 1 extracts the new generation.

def gameOfLife(board: list[list[int]]) -> None:
    m, n = len(board), len(board[0])
    for i in range(m):
        for j in range(n):
            live = 0
            for di in range(-1, 2):
                for dj in range(-1, 2):
                    if di == 0 and dj == 0:
                        continue
                    ni, nj = i + di, j + dj
                    if 0 <= ni < m and 0 <= nj < n and board[ni][nj] % 2 == 1:
                        live += 1
            if board[i][j] == 1 and live in (2, 3):
                board[i][j] = 3
            elif board[i][j] == 0 and live == 3:
                board[i][j] = 2
    for i in range(m):
        for j in range(n):
            board[i][j] >>= 1

Notice the logic: a live cell that should survive gets upgraded from 1 to 3 (bit 1 set). A dead cell that should become alive gets upgraded from 0 to 2 (bit 1 set). Cells that stay dead (0) or die (1) are left untouched because their new state is 0, and 0 >> 1 = 0 and 1 >> 1 = 0.

Step-by-step walkthrough

Complexity analysis

Time: We visit every cell once to count neighbors and encode the transition, then visit every cell once more to right-shift. Each neighbor count examines at most 8 cells. Total work is O(m * n).

Space: The encoding stores both old and new state inside the existing board. No extra arrays, no sets, no queues. Just a few loop variables. That is O(1) extra space.

The building blocks

In-place state encoding

The core idea is packing two pieces of information into a single integer. You have seen this before: the "first missing positive" problem negates values to mark indices as visited, and "set matrix zeroes" repurposes the first row and column as markers. Here you use bit positions instead of sign flips or sentinel values, but the principle is the same: when the problem says "O(1) space," look for unused capacity in the existing data.

# Encode: store new state in bit 1, keep old state in bit 0
if should_survive:
    board[i][j] = 3   # binary 11
elif should_be_born:
    board[i][j] = 2   # binary 10

# Decode: right-shift drops the old state, leaving only the new
board[i][j] >>= 1

This bit-packing technique generalizes nicely. If you needed to track three generations at once, you could use bits 0, 1, and 2. The idea scales as long as your integer type has enough bits.

Neighbor counting in a grid

Scanning all 8 neighbors of a cell is a pattern you will use in dozens of grid problems: flood fill, number of islands, minesweeper, and more.

for di in range(-1, 2):
    for dj in range(-1, 2):
        if di == 0 and dj == 0:
            continue
        ni, nj = i + di, j + dj
        if 0 <= ni < m and 0 <= nj < n:
            # process neighbor at (ni, nj)

The nested loop over [-1, 0, 1] for both directions gives all 8 neighbors. Skipping (0, 0) avoids counting the cell itself. The bounds check 0 <= ni < m and 0 <= nj < n handles edges and corners without special cases. This compact pattern replaces eight separate if-statements and is much less error-prone.

Edge cases

• All dead cells: no cell has 3 neighbors, so nothing changes. The board stays all zeros.
• All alive cells: interior cells have 8 neighbors and die from overpopulation. Edge cells have 5 neighbors and also die. Corner cells have 3 neighbors and survive. Only the four corners remain alive on a board larger than 2x2.
• Single row or single column: each cell has at most 3 neighbors (or 2 for corners, 1 for a 1x2 board). The rules still apply. You just see fewer births since hitting 3 neighbors is rare.
• 1x1 board: the single cell has zero neighbors. If alive, it dies (fewer than 2 neighbors). If dead, it stays dead. The result is always [[0]].

From understanding to recall

You understand the encoding now, but the details (which value means "born," which means "survives," the right-shift at the end) are easy to mix up under pressure. The fix is repetition. Write the solution from scratch: the neighbor-counting loop, the two encoding assignments, the final right-shift pass. Do it today, again tomorrow, again in three days. After a few reps, the bit layout becomes second nature. You see "Game of Life" and the four values (0, 1, 2, 3) just click into place.

State encoding and neighbor counting are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the details stick.

Related posts

• Set Matrix Zeroes - Another in-place matrix modification that repurposes existing cells as markers instead of allocating extra storage
• Number of Islands - Grid traversal with neighbor counting, the same 8-direction scan pattern you use here
• Surrounded Regions - Changing grid cell states in place based on connectivity rules, a similar "mark then update" two-pass strategy