Game of Life

Given a 2D grid of 0s and 1s representing dead/live cells, update the board in-place to the next state according to Conway's Game of Life rules.

Rules for each cell (based on 8 neighbors):

• Live cell with <2 live neighbors dies.
• Live cell with 2 or 3 live neighbors lives.
• Live cell with >3 live neighbors dies.
• Dead cell with exactly 3 live neighbors becomes alive.

Function signature

func GameOfLife(board [][]int)

Inputs / outputs

• board: 2D grid of 0/1 values.
• Return: nothing; modify board in-place.

Example

board = [
  [0,1,0],
  [0,0,1],
  [1,1,1],
  [0,0,0]
]

Constraints

• 0 <= m, n <= 1000

Core idea (near-solution)

To update in-place, encode both current and next state in the same cell:

• 0 -> 0 (stays dead)
• 1 -> 1 (stays live)
• 1 -> 0 (dies) encode as 2
• 0 -> 1 (becomes live) encode as 3

Then do a second pass to convert:

• cell == 2 -> 0
• cell == 3 -> 1

Invariant: when counting neighbors, use cell % 2 to read the original state.

Algorithm (step-by-step)

1. For each cell, count live neighbors using board[r][c] % 2.
2. Apply the rules and encode transitions with 2 or 3.
3. Second pass: replace 2 with 0 and 3 with 1.

Correctness sketch

• Invariant: when counting neighbors, use cell % 2 to read the original state.
• Boundary/marker invariants ensure each cell is processed correctly.
• In-place encodings preserve original state until updates are finalized.
• Thus the final matrix matches the required transformation.

Trace (hand walkthrough)

Example input:
board = [
  [0,1,0],
  [0,0,1],
  [1,1,1],
  [0,0,0]
]

Walk:
- cell (0,1)=1 has neighbors {0,0,0,0,0,1,1,0} -> 2 live -> stays 1
- cell (1,0)=0 has neighbors {0,1,0,0,1} -> 2 live -> stays 0
- cell (1,1)=0 has neighbors {0,1,0,0,1,1,1,0} -> 5 live -> stays 0
- next board becomes [[0,0,0],[1,0,1],[0,1,1],[0,1,0]]

Pitfalls to avoid

• Counting neighbors using the updated state instead of original.
• Forgetting the second pass.

Complexity

• Time: O(m*n)
• Extra space: O(1)

Implementation notes (Go)

• Encode old/new state with bits (bit0 old, bit1 new).
• Count neighbors with cell & 1, then shift right to finalize.