Game of Life
Medium In-place state encoding
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Compute the next generation of Conway's Game of Life on a grid, in place. All cells update at the same time based on their eight neighbours.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: compute the next generation, where every cell updates at the same time.
Why this works: keep the old state in bit 0 and write the new state into bit 1. Neighbours read bit 0 only; at the end shift every cell right.
Example: live cell with 1 live neighbour
old bit 1, dies → new bit 0 → value stays 01after shifting → 0 (dead)
✦Hints open one at a time
↗Approach
For each cell count live neighbours using only bit 0 (the old state). Decide the next state (live with 2 or 3 neighbours, dead with exactly 3 becomes live) and set bit 1. Finally replace each cell with its bit 1.
</>Solution (Java)
class Solution {
public void gameOfLife(int[][] board) {
int m = board.length, n = board[0].length;
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
int live = 0;
for (int dr = -1; dr <= 1; dr++)
for (int dc = -1; dc <= 1; dc++) {
if (dr == 0 && dc == 0) continue;
int rr = r + dr, cc = c + dc;
if (rr >= 0 && rr < m && cc >= 0 && cc < n) live += board[rr][cc] & 1; // old state only
}
boolean alive = (board[r][c] & 1) == 1;
if ((alive && (live == 2 || live == 3)) || (!alive && live == 3)) board[r][c] |= 2;
}
}
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++) board[r][c] >>= 1; // new state becomes current
}
}!Common mistake
Updating cells directly, so later cells see a mix of old and new neighbours.
- Time: O(m·n).
- Space: O(1).