Game of Life

The key idea

Every cell must update from the ORIGINAL neighbor states at once. Encode each transition in the cell itself with a second bit so old and new state coexist: read the low bit for the original value, write the high bit for the next value, then decode in a second pass — no copy of the board needed.

Problem

The board is an m x n grid of cells, where each cell has an initial state: live (represented by a 1) or dead (represented by a 0). Each cell interacts with its eight neighbors (horizontal, vertical, and diagonal) using the following four rules (taken simultaneously):

1. Any live cell with fewer than two live neighbors dies, as if caused by under-population.
2. Any live cell with two or three live neighbors lives on to the next generation.
3. Any live cell with more than three live neighbors dies, as if by over-population.
4. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

The next state of the board is determined by applying the above rules simultaneously to every cell in the current state of the m x n grid board. In this process, births and deaths occur simultaneously. Given the current state of the board, update the board to reflect its next state.

Note that you do not need to return anything. Make the changes in place. Could you solve it in place using the original board and only constant extra memory?

Constraints

m == board.length
n == board[i].length
1 <= m, n <= 25
board[i][j] is 0 or 1.

Examples

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]]

Input: board = [[1,1],[1,0]] Output: [[1,1],[1,1]]

Complexity

Time: O(m * n) Space: O(1)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →