Statement▼
The Game of Life, also known simply as Life, is a cellular automaton introduced by British mathematician John Horton Conway in 1970.
We are given an
1→ Alive cell0→ Dead cell
Each cell interacts with its eight neighbors (horizontal, vertical, and diagonal) according to the following rules:
An alive cell with fewer than 2 alive neighbors dies → underpopulation.
An alive cell with 2 or 3 alive neighbors survives → lives to the next generation.
An alive cell with more than 3 alive neighbors dies → overpopulation.
A dead cell with exactly 3 alive neighbors becomes an alive cell → reproduction.
The board is updated using the above rules, with all updates applied simultaneously across the board. This means the next state of the grid is determined from the current state without interference from ongoing updates.
Given the current state of the board, your task is to update the board to reflect its next state.
Note: You do not need to return anything.
Constraints:
m== board.lengthn== board[i].length1≤m,n≤25 board[i][j]is either0or1.
Solution
The core intuition is to update all cells simultaneously without corrupting neighbor counts. We encode transitions in place: 1 means alive (and may stay alive), -1 means was alive and will die (underpopulation/overpopulation), 0 means dead (and may stay dead), and 2 means was dead and will become alive (reproduction). While counting neighbors, we only care about the original state, so we test abs(board[r][c]) == 1. This is true for 1 and -1 (originally alive) and false for 0 and 2 (originally dead). With that, we finish a full pass marking transitions, then a quick second pass to normalize to 0 or 1.
Using the intuition above, we implement the algorithm as follows:
Store the board’s dimensions in
rowsandcols.Define an array
neighbors = {-1, 0, 1}. The Cartesian product{−1,0,1} × {−1,0,1}gives the relative offsets to all eight neighboring cells around a given cell. We skip the(0, 0)pair as it represents the cell itself. This allows us to systematically check every neighbor’s state when counting alive cells.Iterate over every cell
(row, col)in the grid. For each cell:Initialize a counter
liveNeighbors = 0.To count alive neighbors, loop
i = 0..2andj = 0..2to form a relative offset(neighbors[i], neighbors[j]):Compute the neighbor’s coordinates:
r = row + neighbors[i]andc = col + neighbors[j].If
(r, c)is in bounds andabs(board[r][c]) == 1(originally alive), incrementliveNeighbors.
After counting
liveNeighbors, apply the Game of Life rules using the cell’s original state (the current value before any normalization):If
board[row][col] == 1andliveNeighborsis less than2(underpopulation) or greater than3(overpopulation), mark it as-1to encode alive → dead.Otherwise, if
board[row][col] == 0andliveNeighborsis3, mark it as2to encode dead → alive (reproduction).Otherwise, leave the cell unchanged (
1stays1,0stays0).
Iterate through the
boardagain to finalize the next generation by normalizing each cell back to0or1:If
board[row][col] > 0(values1or2), set it to1.Otherwise (for values
0or-1), set it to0.
The normalized
boardnow represents the next state after applying the rules simultaneously.
Let’s look at the following illustration to get a better understanding of the solution: