Game of Life
Medium · Matrix · Array · Matrix · Simulation
Problem
You are given an m x n board for Conway’s Game of Life, where 1 is a live cell and 0 a dead one. Each cell has up to eight neighbors (horizontal, vertical and diagonal). The next generation is computed from the current one, for all cells at once:
- A live cell with fewer than two or more than three live neighbors dies.
- A live cell with two or three live neighbors survives.
- A dead cell with exactly three live neighbors becomes alive.
Update board in place to its next state. Every decision must use the neighbor counts of the current generation, not values you have already updated. Your function returns nothing; the tests check board after the call.
Examples
Input: board = [[0,1,0],[0,1,0],[0,1,0]] Output: [[0,0,0],[1,1,1],[0,0,0]]
A vertical blinker turns horizontal: the ends die and the middle row’s side cells are born.
Input: board = [[1,1,0],[1,0,0],[0,0,0]] Output: [[1,1,0],[1,1,0],[0,0,0]]
The dead cell (1,1) has three live neighbors and is born; each of the three live cells has two live neighbors and survives.
Constraints
- m == len(board), n == len(board[i])
- 1 <= m, n <= 25
- board[i][j] is 0 or 1
Approaches
- Baseline: count from a copy of the board — time O(m · n), space O(m · n)
Follow-up
What if the board is unbounded, or huge and mostly empty? Store only the live cells in a set and count neighbors with a dictionary (see the use case “Live cells on an unbounded plane after k steps”). And if the edges wrap around, use (r + dr) % m.
Related problems
Start free on Cariara · Coding problems · System design studio
