255. Game of Life
The board is an m × n grid of cells, each either alive (1) or dead (0). One tick advances the whole grid at once, using Conway's rules — every cell's fate is decided from the current board, before any update lands:
- A live cell keeps living only when it has 2 or 3 live neighbors; with fewer it dies of isolation, with more it dies of overcrowding.
- A dead cell springs to life exactly when 3 of its neighbors are alive.
A cell's neighbors are the up-to-8 cells touching it horizontally, vertically, or diagonally. The board does not wrap around, so edge and corner cells simply have fewer neighbors.
The function receives board (a list of m rows, each a list of n integers that are 0 or 1) and returns the board one generation later. The update must be simultaneous — a cell's freshly computed value must never leak into a neighbor's count within the same tick.
Example 1:
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]]
Explanation: The lone cell at row 0 has only one live neighbor, so it dies. The dead cell at (1, 0) touches exactly three live cells, so it is born. Applying the rules to every cell simultaneously yields the glider's next step.
Example 2:
Input: board = [[1,1],[1,0]]
Output: [[1,1],[1,1]]
Explanation: Each live cell has exactly 2 live neighbors and survives, and the dead corner touches all 3 live cells, so it comes alive — the block completes itself.
Constraints:
- 1 ≤ m, n ≤ 50
- board[i][j] is 0 or 1
Hints:
Count each cell's live neighbors against the *original* board. The classic bug is updating in place and letting new values contaminate the counts of cells you haven't visited yet.
A full snapshot copy of the board solves it cleanly in O(m·n) extra space: read counts from the copy, write results into the original.
For O(1) extra space, make each cell carry two facts at once: bit 0 = current state, bit 1 = next state. Neighbor counts read `cell & 1`; a final sweep shifts every cell right by one bit.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
Expected output: [[0,0,0],[1,0,1],[0,1,1],[0,1,0]]