Problem Statement
Game of Life
Picture a grid of light bulbs. Each bulb is either on (1, alive) or off (0, dead). To get the next picture, you look at each bulb and its 8 touching neighbors (up, down, left, right, and the 4 corners) and follow 4 rules: (1) an alive cell with fewer than 2 alive neighbors dies, (2) an alive cell with 2 or 3 alive neighbors stays alive, (3) an alive cell with more than 3 alive neighbors dies, (4) a dead cell with exactly 3 alive neighbors turns alive. The catch is that every bulb flips at the same moment, all based on the original picture. So if we change a bulb right away, we ruin the count for its neighbors. We could copy the whole grid first, but the goal here is to do it in-place, meaning no copy. The trick is to use extra number codes that remember both the old value and the new value inside one cell.
Signals to notice
Brute force first
Copy the entire grid, compute next state from the copy. That instinct is useful because it follows the prompt literally, but it usually keeps revisiting work the problem is begging you to organize.
The key insight
encode both the current state and the next state inside the same cell, so you can compute the future without erasing the present. The first pass decides what each cell will become, and the second pass makes that future official. Once you hold onto the right piece of information from moment to moment, the problem feels less like trial and error and more like following a shape that was there all along.
Trace it on board=[[0,1,0],[0,0,1],[1,1,1],[0,0,0]] (m=4, n=3)
Encoding: 0=dead stays dead, 1=alive stays alive, 2=alive->dead, 3=dead->alive. Neighbor count treats values in {1,2} as originally alive (the invariant holds regardless of scan order).
Pass1 live cells: (0,1)=1 has live=1 (only (1,2)) <2 -> set 2 (dies). (1,2)=1 has live=3 -> stays 1.
Pass1 live cells: (2,0)=1 has live=1 (only (2,1)) <2 -> set 2 (dies). (2,1)=1 has live=3 -> stays 1. (2,2)=1 has live=2 -> stays 1.
Pass1 dead-with-3: (1,0)=0 has live=3 ((0,1),(2,0),(2,1)) -> set 3. (3,1)=0 has live=3 ((2,0),(2,1),(2,2)) -> set 3. All other dead cells lack exactly 3 -> stay 0.
Board after Pass1 (encoded): [[0,2,0],[3,0,1],[2,1,1],[0,3,0]]
Pass2 takes each %2: 0->0, 1->1, 2->0, 3->1.
Returns (in-place) board = [[0,0,0],[1,0,1],[0,1,1],[0,1,0]] (matches expected output).What must stay true
All cells must update simultaneously — a cell's next state depends on its CURRENT neighbors, not already-updated ones. Encoding both states in the cell value avoids needing a copy. When you keep that truth intact, each local choice supports the larger solution instead of fighting it.
Shape of the loop
PASS 1 (decide future, keep present):
for each cell (r,c):
live = count neighbors whose value is in {1,2} # 1/2 = originally alive
if cell==1 and (live<2 or live>3): cell = 2 # alive -> dead
elif cell==0 and live==3: cell = 3 # dead -> alive
PASS 2 (commit): for each cell: cell = cell % 2 # 2->0, 3->1Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Updating cells one by one — that uses the new state of already-processed cells, which corrupts the simultaneous update. The encoding trick preserves the original state. Most mistakes here are not about syntax; they come from losing track of what your state, pointer, or structure is supposed to mean.