Why abs(value) == 1?
A dying cell holds −1, and abs(−1) = 1 — it still registers as originally alive. A newborn cell holds 2, and abs(2) ≠ 1 — it still registers as originally dead.
Encode transitions in-place, then decode.
Conway's Game of Life applies four rules simultaneously to every cell in a matrix to produce the next generation. Underpopulation: a live cell with fewer than 2 live neighbors dies. Survival: a live cell with 2 or 3 neighbors lives on. Overcrowding: a live cell with more than 3 neighbors dies. Reproduction: a dead cell with exactly 3 live neighbors becomes alive. The challenge: compute the next state in place, without an extra copy of the board.
Watch the algorithm run
The Simultaneous Update Problem
If you update each cell immediately, later cells see a mix of old and new states when counting neighbors. A cell that should survive might die because its neighbor was already killed, or a dead cell might incorrectly spring to life because a neighbor was just born. Every cell must see the original generation, not the partially-updated board. We need a way to record decisions without destroying the information that remaining cells still need to read.
Transitional Encoding
Transitional codes (−1 for dying, 2 for born) let us record decisions without destroying information that remaining cells need to read.
-
1
Encode transitions
For each cell, count its live neighbors using
abs(value) == 1to read original state. Mark dying cells as−1and newborn cells as2. -
2
Apply the rules
Live cells with fewer than 2 or more than 3 neighbors →
−1(dying). Dead cells with exactly 3 neighbors →2(born). All others stay. -
3
Cleanup pass
Sweep the entire board: convert positive values to 1, everything else to 0. The next generation is now in place.
Why Abs(value) == 1?
Understanding boundary behavior is as important as the main algorithm path.
Border cells
Cells at the edges have fewer than 8 neighbors. The neighbor-counting loop must check array bounds — out-of-bounds neighbors simply don't exist.
Complexity
Time: O(m × n) — two passes over the matrix.
Space: O(1) — encodings stored in-place.