Game of Life
The Game of Life is played on a grid where every cell is either alive (1) or dead (0). Each cell's next state depends on how many of its eight neighbors are currently alive: a live cell with fewer than two or more than three live neighbors dies; a dead cell with exactly three live neighbors becomes alive. Compute the next state for every cell simultaneously , all in place — encode the transition using extra numeric codes in the same cells, then decode them in a second pass, so old and new states never get mixed up mid-calculation.
Constraints
- m == board.length
- n == boardi.length
- 1 ≤ m, n ≤ 25
- boardi[j] is 0 or 1.
Example
board = [[0, 1, 0], [0, 0, 1], [1, 1, 1], [0, 0, 0]][[0, 0, 0], [1, 0, 1], [0, 1, 1], [0, 1, 0]]Explanation Every cell is updated based on how many of its up-to-8 neighbors were alive in the original board, all at once.
In plain terms
- Simultaneously
- Every cell's next state is based on this generation's board, not on cells that were already updated moments earlier.
Encode transitions in extra codes, then decode in a second pass
Start scanning cell by cell, counting each one's live neighbors from the original board.
What happens in this step
board (rows x cols = 4 x 3): [0,1,0] [0,0,1] [1,1,1] [0,0,0]
Steps to visualize
- For each cell, count its live neighbors using the original values only.
- A live cell that becomes dead is marked with a temporary code (-1) instead of being overwritten with 0 right away.
- A dead cell that becomes alive is marked with a temporary code (2) instead of being overwritten with 1 right away.
- Cells whose state does not change are left untouched.
- Once every cell has been marked, sweep the board once more: turn -1 into 0 and 2 into 1.
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
Start scanning cell by cell, counting each one's live neighbors from the original board.
What happens in this step
board (rows x cols = 4 x 3): [0,1,0] [0,0,1] [1,1,1] [0,0,0]
Solution
function gameOfLife(board) {
const rows = board.length;
const cols = board[0].length;
const countLiveNeighbors = (row, col) => {
let count = 0;
for (let dr = -1; dr <= 1; dr++) {
for (let dc = -1; dc <= 1; dc++) {
if (dr === 0 && dc === 0) {
continue;
}
const r = row + dr;
const c = col + dc;
if (r >= 0 && r < rows && c >= 0 && c < cols && Math.abs(board[r][c]) === 1) {
count++;
}
}
}
return count;
};
for (let row = 0; row < rows; row++) {
for (let col = 0; col < cols; col++) {
const liveNeighbors = countLiveNeighbors(row, col);
const isAlive = board[row][col] === 1;
if (isAlive && (liveNeighbors < 2 || liveNeighbors > 3)) {
board[row][col] = -1;
} else if (!isAlive && liveNeighbors === 3) {
board[row][col] = 2;
}
}
}
for (let row = 0; row < rows; row++) {
for (let col = 0; col < cols; col++) {
if (board[row][col] === -1) {
board[row][col] = 0;
} else if (board[row][col] === 2) {
board[row][col] = 1;
}
}
}
return board;
}- Time
- O(m * n)
- Space
- O(1)
Test cases
| Input | Expected | Covers |
|---|---|---|
board = [[0, 1, 0], [0, 0, 1], [1, 1, 1], [0, 0, 0]] | [[0, 0, 0], [1, 0, 1], [0, 1, 1], [0, 1, 0]] | example from the docstring |
board = [[0]] | [[0]] | smallest valid input, an isolated dead cell |
board = [[1]] | [[0]] | an isolated live cell dies from having no neighbors |
board = [[1, 1], [1, 1]] | [[1, 1], [1, 1]] | a stable 2x2 block that never changes |
board = [[0, 1, 0], [0, 1, 0], [0, 1, 0]] | [[0, 0, 0], [1, 1, 1], [0, 0, 0]] | the classic blinker oscillator flipping orientation |
board = [[0, 0], [0, 0]] | [[0, 0], [0, 0]] | a fully dead board stays dead |