← DSA Atlas
Dedicated problem page · #289

Game of Life

MediumMatrix and SimulationIn-place bit-encoded next stateSimultaneous state transition (bit flags)
Solve on LeetCode ↗
289
MediumMatrix and SimulationSimultaneous state transition (bit flags)In-place bit-encoded next state

Game of Life

Given an m x n board of cells that are live (1) or dead (0), compute the next state under Conway's Game of Life rules applied simultaneously to every cell, and update the board in place.

Open official problem prompt ↗
In plain English

Advance the whole grid one generation of Conway's Game of Life at once, without a second board.

Picture it like this

Like everyone in a stadium deciding to stand or sit at the same signal based on their current neighbors; you must read everyone's present pose before anyone moves.

Example
Input
board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
Output
[[0,0,0],[1,0,1],[0,1,1],[0,1,0]]
Why
Each cell's next value depends only on its eight neighbors in the original board; applying the survival/birth rules everywhere at once yields this grid.
Constraints
m == board.lengthn == board[i].length1 <= m, n <= 25board[i][j] is 0 or 1
Pattern lesson

See the pattern, then code

In-place bit-encoded next state
Recognition clue

Cells that must all update based on their current neighbors, followed by an in-place / O(1) space ask, signals encoding both old and new states in the same cell using extra bits.

↗
Matrix and Simulation

Rotations, boundary walks, direction changes, or careful in-place state updates.. Bit 0 holds the current state and bit 1 holds the next state. Because we only ever read bit 0 while writing bit 1, every cell still sees its neighbors' original values; a final pass shifts each cell right to reveal the next state.

New words, made simpleKnow these before the algorithm
Live neighbor
One of the up to eight adjacent cells that is currently alive.
Bit encoding
Using bit 0 for the current state and bit 1 for the next state within one integer.
Simultaneous update
All cells transition based on the same original snapshot, not on partially-updated values.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Copy the board first

Correct and simple but uses linear extra space.

Compute the next state into a fresh copy, then assign back.

Time O(m*n)Space O(m*n)
Best choiceTwo-bit in-place encoding

Constant space and satisfies the follow-up.

Pack the next state into bit 1 while bit 0 preserves the current state for neighbors to read, then shift.

Time O(m*n)Space O(1)
The rule we keep true

Invariant

Throughout the first pass, bit 0 of every cell still holds its original state, so neighbor counts are always computed against the true previous generation.

Why this is correct

Reasoning

Neighbor counting reads only value & 1 (the low bit), which is never modified during the pass; the next state is written into the high bit via | 2. Since the low bit is untouched, order of visitation cannot corrupt any count. The final right shift discards the old low bit and promotes the new high bit.

The algorithm in three movesSay these aloud before coding
1For each cell, count live neighbors by testing bit 0 (value & 1) of the eight neighbors

cell(1,0) dead, live nbrs=3 -> becomes live (encode 2)

2Apply the rules: a live cell with 2 or 3 neighbors and a dead cell with exactly 3 neighbors become live next; set bit 1 (value | 2) in those cases

cell(2,0) live, live nbrs=1 -> dies

3After scanning all cells, right-shift every cell by 1 to drop the old state and keep the new one

after pass: values hold old|new<<1

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
00
11
02
03
04
15
16
17
18
09
010
011
1 · Readdead cell
2 · AskLive neighbors?
3 · Update stateneighbors (0,1),(1,0),(1,1) -> 1 live
4 · Resultstays dead, low bit 0
Key takeaway

The live cells (indices flattened row-major) whose neighborhoods drive the next generation.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 5-12Count live neighbors

    Iterate the eight offsets, skip the center, bound-check, and test the low bit so counts reflect the original board.

  2. 2
    Lines 13-18Encode next state

    Set bit 1 when the cell should be live next; leaving it 0 means dead next.

  3. 3
    Lines 19-21Reveal the generation

    Right shift by one drops the old state and keeps the newly computed state.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Cells on edges and corners with fewer neighbors
  • A board that is all dead (stays all dead)
  • A 1x1 board
  • A stable pattern (block) that does not change
!

Common beginner mistakes

  • Reading board[ni][nj] directly instead of board[ni][nj] & 1, which counts already-encoded next states as live
  • Forgetting the final shift, leaving values of 2 and 3 in the board
  • Overwriting the low bit during the first pass and corrupting later neighbor counts
  • Counting the cell itself as its own neighbor
Check your understanding

Why does using & 1 to read neighbors keep the update simultaneous even though we mutate cells during the pass?

More in Matrix and Simulation

#6Zigzag ConversionRow-index simulation with bouncing direction#48Rotate ImageTranspose then reverse rows#54Spiral MatrixShrinking boundary walk#59Spiral Matrix IIShrinking boundary fill#73Set Matrix ZeroesFirst row/column as marker storage#498Diagonal TraverseAnti-diagonal grouping with alternating sweep