Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Apply Conway's four rules to every cell simultaneously. The naive answer copies the board so reads aren't polluted by writes (O(mn) space). The interview answer encodes the next state in a second bit IN PLACE: keep the current state in bit 0, write the next state into bit 1, read neighbors with `cell & 1`, then in a final pass right-shift every cell. O(mn) time, O(1) extra space.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you see that the update is simultaneous (a classic correctness trap) and whether you can achieve O(1) extra space by encoding the next state without destroying the current state needed by neighbors.
Where candidates slip
Updating cells in place with plain 0/1, so cells processed earlier corrupt the neighbor counts of cells processed later; or counting neighbors with == 1 after some have been overwritten with the next state.
How to stand out
State the simultaneity constraint first, give the O(mn)-copy baseline, then derive the 2-bit in-place encoding and mention the infinite-board follow-up handled with a hash set of live coordinates.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewCount live neighbors using (n & 1)Cell currently live? (cell & 1)LiveDeadExplore the full treeCollapse the tree
How to read it:bit 0 holds the current state, bit 1 holds the next. Reading & 1 always recovers the original value during the first pass.
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Copy the Board (baseline, O(mn) space)
1Hint 1Explore hintHide hint
The danger is that updating a cell to its next value changes the neighbor count seen by cells you process later. How do you guarantee every cell reads the ORIGINAL generation?
2Hint 2Explore hintHide hint
Make a full copy of the board first. Read neighbor counts from the (immutable) copy; write the next state into the original board.
3Hint 3Explore hintHide hint
Because reads and writes target different arrays, order of processing no longer matters — the update is effectively simultaneous.
A · Core idea
The whole difficulty of Game of Life is the word simultaneously. If you overwrite a cell with its next value while scanning, a neighboring cell you visit afterward will count the new value instead of the current one, producing a wrong generation. The simplest way to guarantee correctness is to physically separate the two generations.
How the copy removes the trap. Take a complete snapshot of the board before doing any updates. Then, for each cell, count its live neighbors by reading the snapshot (which never changes) and write the resulting next state into the original board. Because every neighbor read comes from the frozen copy, it doesn't matter what order we process cells in or which originals we've already overwritten — the reads always reflect the current generation. This is the textbook 'double buffering' technique used in graphics and simulations.
Why it's worth presenting even though it isn't optimal. It is unambiguously correct and easy to reason about, so it's the right first thing to say in an interview — it proves you understand the simultaneity requirement before you start being clever about space. Many candidates jump straight to an in-place hack, make a subtle ordering mistake, and can't explain why it's wrong. Leading with the copy shows disciplined thinking.
Its only weakness. It uses O(mn) auxiliary memory for the snapshot. The follow-up explicitly asks to do it in place, which motivates the bit-encoding approach. But on a 25 × 25 board the copy is perfectly acceptable in practice — the optimization is about demonstrating you can avoid the copy, not about a real performance need here.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
board = [[1,1],[1,0]](0,0) live
neighbors live = 2 (from copy) → in {2,3}
stays live → 1[[1,1],[1,1]]C · Code with teaching comments
Reference implementation previewpublic void gameOfLife(int[][] board) { int m = board.length, n = board[0].length; int[][] copy = new int[m][n]; for (int i = 0; i < m; i++) copy[i] = board[i].clone(); int[][] dirs = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};Explore the full codeHide the full code
D · Why it works and complexityO(mn) timeO(mn) spaceOpen the invariant and proofExplore the proofHide the proof
Double buffering — read from a frozen snapshot, write to the live buffer — is the universal cure for 'all cells update at once' bugs. When in doubt about an in-place simultaneous update, reach for the copy first to lock in correctness, then optimize space only if asked.
ComplexityO(mn) time, O(mn) space — Visit each of mn cells, count up to 8 neighbors (constant) → O(mn) time. The snapshot copy uses O(mn) extra space.
E · Edge cases and pitfalls51x1 board [[1]] — No neighbors → live cell dies (0 < 2) → [[0]].Explore edge casesHide edge cases
Edge cases handled
1x1 board [[1]]No neighbors → live cell dies (0 < 2) → [[0]].all deadNo cell has 3 live neighbors → stays all dead.
Pitfalls
- Writing into board while reading board — pollutes neighbor counts (the simultaneity bug).
- Shallow-copying the outer array only (in Java, copy = board copies references) — clone each row.
- Forgetting out-of-bounds neighbors are dead.
Approach 2 of 2 · Optimal
In-Place 2-Bit Encoding (Optimal, O(1) space)
1Hint 1Explore hintHide hint
You don't need a whole copy — you only need to remember each cell's CURRENT value while also recording its NEXT value. A single int has spare bits. Could you store both?
2Hint 2Explore hintHide hint
Use bit 0 for the current state and bit 1 for the next state. Count neighbors with (cell & 1) so you always read the current generation, and record the next state with cell |= 2.
3Hint 3Explore hintHide hint
After processing every cell, do a second pass that right-shifts each cell (cell >>= 1) to drop the old current bit and promote the next-state bit.
A · Core idea
The copy works but spends O(mn) memory just to remember the old generation. The key realization is that we don't need a separate board to hold the next generation — each cell is an int with plenty of unused bits, so we can pack both generations into one cell.
The bit layout. Reserve bit 0 (the ones place) for the current state and bit 1 (the twos place) for the next state. Initially every cell is 0 or 1, so bit 1 is 0 everywhere. There are four encoded values: 00 = dead→dead, 01 = live→dead, 10 = dead→live, 11 = live→live. The crucial property is that cell & 1 always recovers the current state, and cell >> 1 recovers the next state.
Why neighbor reads stay correct. During the first pass we only ever set bit 1 (cell |= 2); we never modify bit 0. So no matter how many neighbors we've already 'updated', counting live neighbors with neighbor & 1 always returns their original current-generation value. That's exactly the simultaneity guarantee the copy gave us — achieved without extra memory, because the old value is preserved untouched in bit 0 while the new value accumulates in bit 1. This is the single insight that makes the in-place solution correct.
Applying the rules. For each cell, count live neighbors live using & 1. If the cell is currently live (cell & 1 == 1) and live is 2 or 3, it survives, so set its next bit: cell |= 2. If the cell is currently dead and live == 3, it reproduces, so again cell |= 2. In every other case the next state is dead, and since bit 1 starts at 0 we simply leave it alone — no clearing needed.
The cleanup pass. After all cells carry their next state in bit 1, a second sweep does cell >>= 1 on every cell. This discards the now-irrelevant current bit and shifts the next-state bit down into bit 0, leaving a clean 0/1 board representing the new generation. Two passes, no auxiliary array.
Why this is the canonical in-place answer. It's the textbook resolution to the follow-up: it keeps time at O(mn), drops space to O(1), and the bit trick generalizes to any simultaneous-update grid where the state set is small enough to encode in spare bits. Mentioning that you could also encode richer transitions (e.g., distinct codes for 'was-live-now-dead') shows command of the technique.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
board = [[1,1],[1,0]]How to read it:A cell already updated to 3 (11) still reports current = 1 to its neighbors via & 1.
[[1,1],[1,1]]C · Code with teaching comments
D · Why it works and complexityO(mn) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
An integer cell can carry two generations at once: low bit = now, high bit = next. Because neighbor counting only reads the low bit and updates only set the high bit, the current generation is never disturbed mid-pass — that's the in-place version of double buffering, paid for in bits instead of bytes.
ComplexityO(mn) time, O(1) space — Two passes over mn cells, each counting ≤ 8 neighbors → O(mn) time. We reuse the board's own integers to hold two generations, so only O(1) extra space.
E · Edge cases and pitfalls71x1 [[1]] — 0 live neighbors → no bit set → shift → [[0]].Explore edge casesHide edge cases
Edge cases handled
1x1 [[1]]0 live neighbors → no bit set → shift → [[0]].[[0,0,0],[0,0,0]]No cell gets bit 1 set; shift leaves all zeros.cell currently dead with 3 live neighborscell goes 0 → |= 2 → 2 (10); shift → 1.
Pitfalls
- Counting neighbors with == 1 instead of & 1 — once a neighbor is encoded as 3, == 1 misses it.
- Forgetting the final >>= 1 pass — board stays in encoded form.
- Clearing bit 0 during the first pass — destroys the current state other cells still need.
- Using values that overflow two bits (e.g., +=) — stick to bitwise OR for the next-state flag.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic void gameOfLife(int[][] board) { int m = board.length, n = board[0].length; int[][] dirs = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}}; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) {Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1In-place update without encoding (the simultaneity bug)
Overwriting board[i][j] with the next 0/1 means a later cell counts this cell's NEW value as a neighbor, not its current value, producing a wrong generation.
Explore the code comparisonHide the code comparison
In-place update without encoding (the simultaneity bug)
Overwriting board[i][j] with the next 0/1 means a later cell counts this cell's NEW value as a neighbor, not its current value, producing a wrong generation.
Don't write this
for i in range(m):
for j in range(n):
live = count_live(board, i, j)
board[i][j] = 1 if (board[i][j] and live in (2,3)) or (not board[i][j] and live == 3) else 0Write this instead
for i in range(m):
for j in range(n):
live = count_live_current(board, i, j) # uses & 1
if board[i][j] & 1:
if live in (2, 3): board[i][j] |= 2
else:
if live == 3: board[i][j] |= 2
for i in range(m):
for j in range(n):
board[i][j] >>= 12Counting neighbors with == 1 instead of & 1
Once a neighbor has its next-state bit set it becomes 2 or 3. Comparing == 1 then misses currently-live cells encoded as 3, undercounting neighbors.
Explore the code comparisonHide the code comparison
Counting neighbors with == 1 instead of & 1
Once a neighbor has its next-state bit set it becomes 2 or 3. Comparing == 1 then misses currently-live cells encoded as 3, undercounting neighbors.
Don't write this
if (board[ni][nj] == 1) live++;Write this instead
if ((board[ni][nj] & 1) == 1) live++;3Forgetting the shift-down pass
After the first pass the board holds encoded values (0,1,2,3). Without the final cell >>= 1, the output is the two-bit encoding, not the next generation.
Explore the code comparisonHide the code comparison
Forgetting the shift-down pass
After the first pass the board holds encoded values (0,1,2,3). Without the final cell >>= 1, the output is the two-bit encoding, not the next generation.
Don't write this
// first pass sets bit 1, then return without shiftingWrite this instead
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
board[i][j] >>= 1;Revise
Carry the pattern into the interview
Pattern to remember
In-place 2-bit state encoding (next state in the high bit)
Code pattern to memorize
// bit0 = current, bit1 = next
live = count of neighbors with (cell & 1) == 1
if (cell & 1) and live in {2,3}: cell |= 2 // stays/becomes live
if !(cell & 1) and live == 3: cell |= 2 // reproduction
// final pass: cell >>= 1Rules to remember
- 1Update must be simultaneous — every cell's next state depends only on the CURRENT generation, so you can't overwrite cells in place naively.
- 2Encode two generations in two bits: bit 0 = current, bit 1 = next. Read neighbors with
cell & 1, write next withcell |= 2. - 3Because you only ever set bit 1 (never touch bit 0) in the first pass, neighbor reads stay correct throughout.
- 4Do a second pass that does
cell >>= 1to promote the next state to the current state. - 5Only count live neighbors equal to 1 in bit 0 — encoded values 2 or 3 still read as their original current state via
& 1.
Use this pattern when
- Cellular-automaton / grid simulation where all cells update at once
- Need an in-place update but reads must see the old values
- Any 'compute next state from current state of neighbors' on a matrix
- Asked to optimize matrix space from O(mn) to O(1)
Choose another pattern when
- Updates are sequential / order-dependent → can't batch, no bit trick
- State has more than a few values → bit encoding doesn't fit, use a copy
- Board is effectively infinite → store only live cells in a hash set
- You're allowed O(mn) space and clarity matters more → just copy the board
Interview takeaway
The reusable trick is storing the NEXT state in unused high bits so the CURRENT state survives for neighbor reads, then doing a cleanup pass to shift. It generalizes to any in-place simultaneous-update grid problem — the key realization is that one int can hold two generations at once.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternIn-place simultaneous grid update via spare-bit encoding (next state in the high bit) plus a cleanup shift pass. Recognise it whenever every cell must update at once from neighbors' current values AND O(1) space is demanded. The copy/double-buffer is the correctness baseline; the bit trick is the space optimization. For an infinite board, switch to a hash set of live coordinates.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Set Matrix ZeroesAnother in-place matrix problem — use the first row/column as markers instead of an O(mn) copy.
- Number of IslandsComing soonGrid traversal of neighbors — flood fill rather than simultaneous update.
- Rotting OrangesComing soonTime-stepped grid simulation, but spread is via BFS layers rather than fixed rules.
- Walls and GatesComing soonMulti-source BFS over a grid — neighbor propagation with distances.