Intuition
Because all cells update simultaneously, we must read the old state while writing the new one. Encode the next state in the second bit (value 2) while the current state stays in bit 1. After scanning, shift every cell right by one to reveal the next generation.
Explanation
Idea
The rules depend on each cell's current neighbors, but every cell changes at once — so we can't overwrite in place naively. Trick: store two states per cell using two bits. Bit 0 (value 1) keeps the current state; bit 1 (value 2) records the next state. Reading board[i][j] & 1 always sees the original, while the next state accumulates in bit 1.
After processing the whole grid, board[i][j] >>= 1 drops the old state and leaves the new one.
Algorithm
- For each cell, count live neighbors via
board[ni][nj] & 1. - Set bit 1 (
|= 2) when the cell should be live next: a live cell with 2–3 neighbors, or a dead cell with exactly 3. - After all cells,
board[i][j] >>= 1everywhere.
Worked example: [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
Applying the four rules simultaneously yields [[0,0,0],[1,0,1],[0,1,1],[0,1,0]].
Complexity
- Time: O(m·n) — constant work (8 neighbors) per cell.
- Space: O(1) — updated in place.
Implementation
class Solution {
public int[][] gameOfLife(int[][] board) {
int m = board.length, n = board[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int live = 0;
for (int di = -1; di <= 1; di++) {
for (int dj = -1; dj <= 1; dj++) {
if (di == 0 && dj == 0) {
continue;
}
int ni = i + di, nj = j + dj;
if (ni >= 0 && ni < m && nj >= 0 && nj < n && (board[ni][nj] & 1) == 1) {
live++;
}
}
}
if ((board[i][j] & 1) == 1 && (live == 2 || live == 3)) {
board[i][j] |= 2;
} else if ((board[i][j] & 1) == 0 && live == 3) {
board[i][j] |= 2;
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
board[i][j] >>= 1;
}
}
return board;
}
}