#289 Game of Life
the problem
In plain words
An m × n board is one generation of Conway's Game of Life: 1 means alive, 0 means dead. Each cell looks at its 8 neighbours (sides and corners; there is nothing beyond the edges). A live cell with 2 or 3 live neighbours stays alive, and with any other count it dies. A dead cell with exactly 3 live neighbours comes alive. Every cell changes at the same moment. Replace the board with the next generation, in place.
in board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
out [[0,0,0],[1,0,1],[0,1,1],[0,1,0]]
This shape is the famous glider: on an endless board it travels one cell diagonally every 4 generations.
in board = [[1,1],[1,0]]
out [[1,1],[1,1]]
The dead corner has exactly 3 live neighbours, so it comes alive.
- 1 ≤ m, n ≤ 25
- board[i][j] is 0 or 1
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternIn-place markersSimulation
where this runsGames and video players use double buffering: the next frame is drawn into a back buffer while the screen still shows the front one, the same old-versus-new split as this problem.
Every cell must be decided from the old board. Cells only use bit 0 (0 or 1), so bit 1 can hold the next state while neighbours keep reading bit 0. One more pass shifts the next state into place.
solutions
From brute force to optimal
Copy the board. Count each cell's live neighbours in the copy and write the result into the board.
- old = deep copy of board.
- For each cell, count live neighbours in old.
- board[r][c] = (live == 3 || (live == 2 && old[r][c] == 1)) ? 1 : 0.
8 neighbour checks per cell.
The copy of the board.
class Solution { public void gameOfLife(int[][] board) { int m = board.length, n = board[0].length; int[][] old = new int[m][]; for (int r = 0; r < m; r++) old[r] = board[r].clone(); // freeze this generation for (int r = 0; r < m; r++) { for (int c = 0; c < n; c++) { int live = 0; for (int dr = -1; dr <= 1; dr++) for (int dc = -1; dc <= 1; dc++) { int nr = r + dr, nc = c + dc; if ((dr != 0 || dc != 0) && nr >= 0 && nr < m && nc >= 0 && nc < n) live += old[nr][nc]; } board[r][c] = live == 3 || (live == 2 && old[r][c] == 1) ? 1 : 0; // write the next one } } }}Bit 0 = alive now, bit 1 = alive next. Pass 1 sets bit 1 using only bit 0 of the neighbours; pass 2 shifts every cell right by one.
- For each cell, live = sum of (neighbour & 1) over the 8 directions.
- If live == 3, or the cell is alive and live == 2: board[r][c] |= 2.
- Then board[r][c] >>= 1 for every cell.
8 neighbour checks per cell, plus one shift per cell.
The next state lives in the cell's spare bit.
class Solution { private static final int[][] DIRS = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}}; public void gameOfLife(int[][] board) { int m = board.length, n = board[0].length; for (int r = 0; r < m; r++) { // pass 1: decide every cell for (int c = 0; c < n; c++) { int live = 0; for (int[] d : DIRS) { int nr = r + d[0], nc = c + d[1]; if (nr >= 0 && nr < m && nc >= 0 && nc < n) live += board[nr][nc] & 1; // bit 0 = now } boolean alive = (board[r][c] & 1) == 1; if (live == 3 || (alive && live == 2)) { board[r][c] |= 2; // bit 1 = alive in the next generation } } } for (int r = 0; r < m; r++) { // pass 2: next becomes now for (int c = 0; c < n; c++) board[r][c] >>= 1; } }}Dry run
in the room
How to say it in the interview
talk track
- Restate the rule compactly: alive next ⇔ live == 3, or (alive now and live == 2).
- Explain why a single in-place pass fails: later cells would count already-updated neighbours.
- Offer the copy first, then the 2-bit encoding for O(1) space. Mention that neighbours read
& 1.
traps
- Updating cells in a single pass, so later cells count new values instead of old ones.
- Counting the cell itself as its own neighbour.
- Counting neighbours with
board[nr][nc]instead ofboard[nr][nc] & 1in the in-place version: a 2 or 3 would count as 2 or 3 live cells. - Wrapping around the edges. Cells outside the board simply don't exist here.
what they ask next
Follow-ups
What if the board is infinite?
Store only the live cells, for example in a HashSet<Long> with key (long) r << 32 | (c & 0xffffffffL). Each live cell adds 1 to its 8 neighbours' counts in a HashMap. The next generation is every cell with count 3, or count 2 that is alive now. Work grows with the live cells, not the board.
The board is too big for memory and arrives row by row?
A cell needs only the rows above and below it. Keep a rolling window of 3 rows and write each finished row out.
before you submit
Edge cases to test
- 1 × 1 board: no neighbours, so a live cell dies.
- Edge cells have 5 neighbours and corner cells only 3. Check the bounds; don't wrap around.
- A 2 × 2 block of live cells never changes.
- A line of 3 live cells (a blinker) flips between a row and a column.
practise next
Similar problems
- #73Set Matrix ZeroesMediumin Matrices
- #994Rotting OrangesMediumin Graphs
- #200Number of IslandsMediumin Graphs