LeetCode #289 Medium

Game of Life

Advance a board of live and dead cells by one generation of Conway's rules, in place.

arraymatrixsimulation

02

Intuition

💡

The instinct is to loop over the board and write each cell's new value the moment you compute it. That destroys the problem. The rules say every cell is updated simultaneously, but an in-place write means a cell you bring to life at (0,1) is then counted as a live neighbour when you judge (0,2), which has not been visited yet. Your board evolves like a wave spreading left to right instead of a generation flipping at once, and a blinker will come out mangled. The obvious repair is a full copy of the board, which is correct but spends O(m*n) memory on what is really a bookkeeping problem. The better fix is to notice that a cell only needs to hold two bits: keep the old state in bit 0 and write the new state into bit 1, so every neighbour count reads board[i][j] & 1 and always sees the original generation. Then a second pass shifts everything right by one. The invariant is that throughout pass one, bit 0 of every cell is still untouched, so the board you are reading is the board you started with.

03

Approach

1

Understand why in place naively fails

The four rules are stated over a single fixed snapshot. If you overwrite as you go, cells later in scan order read a mixture of old and new values, and the mixture depends on your traversal order, which is not part of the problem at all. Any correct solution must guarantee that every neighbour count is taken against the original board.

2

Pack both generations into one integer

A cell is only 0 or 1, so bit 1 is free. Leave the old state in bit 0 and set bit 1 when the cell should be live next generation. Count neighbours with (board[nr][nc] & 1), which masks off anything pass one has written and returns the untouched original. Nothing is destroyed during the pass, which is exactly the property the naive version lacks.

3

Second pass to shift the new state down

Once every cell has been judged, walk the board once more and do board[i][j] >>= 1. Bit 1 slides into bit 0 and the stale generation falls off the end. Two linear passes cost the same asymptotically as one and use only a constant number of extra variables, so the space requirement is genuinely O(1).

04

Solution & live demo

python

▶1class Solution:
▶2    def gameOfLife(self, board: List[List[int]]) -> None:
▶3        rows, cols = len(board), len(board[0])
▶4        for r in range(rows):
▶5            for c in range(cols):
▶6                live = 0
▶7                for dr in (-1, 0, 1):
▶8                    for dc in (-1, 0, 1):
▶9                        if dr == 0 and dc == 0:
▶10                            continue
▶11                        nr, nc = r + dr, c + dc
▶12                        if 0 <= nr < rows and 0 <= nc < cols:
▶13                            live += board[nr][nc] & 1
▶14                if board[r][c] & 1:
▶15                    if live == 2 or live == 3:
▶16                        board[r][c] |= 2
▶17                elif live == 3:
▶18                    board[r][c] |= 2
▶19        for r in range(rows):
▶20            for c in range(cols):
▶21                board[r][c] >>= 1
▶22        return None

05

Edge cases

Cells on an edge or corner

Bounds-check each of the eight offsets; missing neighbours count as dead, which is what the fewer in-range cells naturally give.

Still life such as a 2x2 block

Each cell has exactly 3 live neighbours and survives, so the board is unchanged after both passes.

All dead board

No cell reaches 3 neighbours, nothing is born, and the shift pass leaves every cell at 0.

1x1 board

The single cell has 0 neighbours, so a live cell dies of underpopulation and a dead one stays dead.

06

Complexity

Time

O(m * n)

Space

O(1)

Each cell is touched twice and reads at most 8 neighbours, a constant factor; no auxiliary board is allocated.