Game of Life Solution

Problem

A 2D grid of cells is either alive (1) or dead (0). At each step, every cell updates simultaneously according to four rules: live cells with fewer than 2 or more than 3 live neighbors die; live cells with 2 or 3 live neighbors survive; dead cells with exactly 3 live neighbors come to life. Given the current grid, update it in-place to reflect the next generation.

Input:           Output:
0 1 0            0 0 0
0 0 1    →       1 0 1
1 1 1            0 1 1
0 0 0            0 1 0

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]]
Explanation: Cell (1,0) had 3 live neighbors and became alive; cell (0,1) had only 1 and died.

Intuition

Every cell must change based on its neighbors' current state — not the state after any of them have already updated. If you update cells one by one, later cells read already-changed values and get the wrong neighbor counts. The two solutions differ in how they preserve the original state: one keeps a full copy; the other encodes the "next" state invisibly inside the same integers, using a bit that the neighbor-reading logic ignores.

Approach 1 — Board Copy

Copy the original board before making any changes, then compute each cell's next state by reading from the copy while writing to the original.

Clone the board into a copy array.
For each cell, count live neighbors by reading copy[r][c].
Apply the rules: a cell is alive next round if it has exactly 3 live neighbors, or if it's currently alive with exactly 2.
Write the result directly into board[r][c].

1def gameOfLife(board: list[list[int]]) -> None:
2    rows, cols = len(board), len(board[0])
3    copy = [row[:] for row in board]  # snapshot before any changes
4    directions = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
5
6    for row in range(rows):
7        for col in range(cols):
8            live_neighbors = sum(
9                copy[row + dr][col + dc]
10                for dr, dc in directions
11                if 0 <= row + dr < rows and 0 <= col + dc < cols
12            )
13            # survives if alive with 2-3, or born if dead with exactly 3
14            if live_neighbors == 3 or (copy[row][col] == 1 and live_neighbors == 2):
15                board[row][col] = 1
16            else:
17                board[row][col] = 0

Time: O(m × n) — every cell is visited once.
Space: O(m × n) — the copy array holds the full original board.

Approach 2 — In-Place Bit Encoding

Each cell is 0 or 1, so its value only uses bit 0. We can encode the next state in bit 1 of the same integer without disturbing bit 0 — meaning neighbor reads (cell & 1) still see the original state throughout the first pass.

For each cell, count live neighbors using board[r][c] & 1 to read only the current state.
If the cell will be alive next round, set bit 1: board[r][c] |= 2.
After the full board is processed, shift every cell right by 1: board[r][c] >>= 1.

1def gameOfLife(board: list[list[int]]) -> None:
2    rows, cols = len(board), len(board[0])
3    directions = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
4
5    for row in range(rows):
6        for col in range(cols):
7            live_neighbors = sum(
8                board[row + dr][col + dc] & 1  # bit 0 is always the original state
9                for dr, dc in directions
10                if 0 <= row + dr < rows and 0 <= col + dc < cols
11            )
12            if live_neighbors == 3 or (board[row][col] & 1 == 1 and live_neighbors == 2):
13                board[row][col] |= 2  # write next-alive into bit 1, leave bit 0 intact
14
15    for row in range(rows):
16        for col in range(cols):
17            board[row][col] >>= 1  # drop bit 0; bit 1 becomes the new value

Time: O(m × n) — same single pass over every cell, plus one more pass to shift.
Space: O(1) — all state is encoded directly inside the board's existing integers.

Complexity Summary

Approach	Time	Space	When to use
Board Copy	O(m × n)	O(m × n)	When clarity matters most or the values aren't bounded to 0/1
Bit Encoding	O(m × n)	O(1)	Follow-up interviews asking for in-place; works only when values fit in a single bit

Common Mistakes

Reading updated state from the same board — updating board[r][c] = 1 before all of cell (r,c)'s neighbors have been processed causes adjacent cells to count the new state as if it were the original. This is the entire reason both approaches exist.
Forgetting to mask with & 1 in the bit-encoding approach — after some cells have been tagged with |= 2, reading board[nr][nc] raw returns 2 or 3 for "alive" cells instead of 1, inflating neighbor counts and producing wrong results.
Applying >>=1 during the first pass — shifting cells as you go corrupts bit 0 (the original state) for cells still to be processed; the shift must be a completely separate second pass.
Using >= 2 for the birth rule instead of == 3 — dead cells only come to life with exactly 3 neighbors, not any count ≥ 3.
Omitting the explicit board[r][c] = 0 in the copy approach — if the board could contain values other than 0 and 1, failing to zero out dying cells leaves garbage; even with clean input, the else branch should always be explicit.

Game of Life — Solution