Matrix crash course ↗ · 180

289. Game of Life

Advance Conway's board one generation where every cell updates simultaneously. The O(1)-space trick: pack the next state into bit 1 of each cell while the currentstate stays in bit 0, then shift everything right at the end.

● MediumMatrixIn-placeBit ManipulationTypeScript

PROBLEM What we're solving

Conway's Game of Life. Given an m × n board of 1 (live) / 0 (dead) cells, produce the next generation, applying these rules to all cells at once: a live cell with < 2 or > 3 live neighbors dies; a live cell with 2 or 3 survives; a dead cell with exactly 3 live neighbors is born.
Input: [[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]]

KEY IDEA Two states in one integer using two bits

Insight → The hard part is that updates are simultaneous — if you overwrite a cell, its neighbors can no longer read the original value. Instead of copying the board, store both states in the same cell: keep the current state in bit 0 and write the next state into bit 1. So a cell becomes one of 0 (00, dead→dead), 1 (01, live→dead), 2 (10, dead→live), or 3 (11, live→live). Neighbor counts read value & 1 (the untouched current state). A final pass does value >>= 1 to reveal the next state.

RECIPE Count low bit, write high bit, shift down

1 · Count live neighbors via the low bit. For each cell, scan its 8 neighbors and add board[nr][nc] & 1. Using & 1 reads the original state even after earlier cells have had their high bit set.
2 · Decide and write the next state into bit 1. If the cell is currently live (board[r][c] & 1) and has 2 or 3 live neighbors, it survives → board[r][c] |= 2. If it's dead with exactly 3, it's born → board[r][c] |= 2. Otherwise leave bit 1 as 0 (next state dead). The low bit is never touched.
3 · Reveal the next generation. A second full pass does board[r][c] >>= 1, discarding the old state and leaving only the next state in bit 0.

Classic confusion →people set bit 1 only on "born/survive" cells, then forget that cells which die already have bit 1 = 0, which is exactly the next state (dead) — so no extra work is needed. The error to avoid is counting neighbors with the full value instead of & 1: once you start writing bit 1, a neighbor read as 3 instead of 1 would over-count.

COST Complexity & space reduction

Copy the board

O(m·n)

Simple, but allocates a second full grid.

2-bit in-place encoding

O(1)

O(m·n) time; no extra grid.

Both run in O(m·n) time — every cell looks at a constant 8 neighbors. The naive approach copies the board into a second buffer (so reads always see the original); the bit trick removes that buffer for O(1) extra space.

Pattern transfer →"store two values in one slot" recurs whenever updates must be simultaneous or space is tight: Set Matrix Zeroesreuses row 0 / col 0 as flag storage, and any DP that overwrites a rolling array reads the previous layer before writing the next. Spare bits or marker rows are the go-to when you can't afford a copy.

RUN IT Encode next state in bit 1, then shift everything down

Board (rows separated by ;)

step 0 / 31

STARTApply the rules to every cell simultaneously. Trick: store the next state in bit 1 while the current state stays in bit 0, so neighbors still read the old value via & 1.

1▶function gameOfLife(board: number[][]): void {
2▶  const rows = board.length;
3▶  const cols = board[0].length;
4 
5  // Bit 0 = current state, bit 1 = next state.
6  for (let r = 0; r < rows; r++) {
7    for (let c = 0; c < cols; c++) {
8      let live = 0;
9      for (let dr = -1; dr <= 1; dr++) {
10        for (let dc = -1; dc <= 1; dc++) {
11          if (dr === 0 && dc === 0) continue;
12          const nr = r + dr, nc = c + dc;
13          if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
14          live += board[nr][nc] & 1;   // read CURRENT via low bit
15        }
16      }
17      // Rules: live stays/dies, dead may be born. Write next into bit 1.
18      if ((board[r][c] & 1) === 1) {
19        if (live === 2 || live === 3) board[r][c] |= 2;
20      } else if (live === 3) {
21        board[r][c] |= 2;
22      }
23    }
24  }
25 
26  // Second pass: drop the old state, shift next state down.
27  for (let r = 0; r < rows; r++) {
28    for (let c = 0; c < cols; c++) {
29      board[r][c] >>= 1;
30    }
31  }
32}

State
encoding: bit0 = now, bit1 = next
init

current celllive neighbor (low bit = 1)cell whose value just changed

slowfast

TYPESCRIPT The solution, annotated

gameOfLife.ts
function gameOfLife(board: number[][]): void {
  const rows = board.length;
  const cols = board[0].length;

  // Bit 0 = current state, bit 1 = next state.
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      let live = 0;
      for (let dr = -1; dr <= 1; dr++) {
        for (let dc = -1; dc <= 1; dc++) {
          if (dr === 0 && dc === 0) continue;
          const nr = r + dr, nc = c + dc;
          if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
          live += board[nr][nc] & 1;   // read CURRENT via low bit
        }
      }
      // Rules: live stays/dies, dead may be born. Write next into bit 1.
      if ((board[r][c] & 1) === 1) {
        if (live === 2 || live === 3) board[r][c] |= 2;
      } else if (live === 3) {
        board[r][c] |= 2;
      }
    }
  }

  // Second pass: drop the old state, shift next state down.
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      board[r][c] >>= 1;
    }
  }
}

Reading it block by block

Lines 5–7 — iterate every cell. We process the whole board, but crucially we do not overwrite the current state. The comment names the contract: bit 0 holds the current value, bit 1 will hold the next value.

Lines 8–17 — count live neighbors. Scan the 8 surrounding cells, skipping (0,0) and out-of-bounds. Add board[nr][nc] & 1 — the & 1 masks off any next-state bit already written, so we always count the original liveness.

Lines 19–24 — apply the rules into bit 1. If the cell is currently live (board[r][c] & 1) and has 2 or 3 neighbors, it survives, so set bit 1 with |= 2. A dead cell with exactly 3 neighbors is born, likewise |= 2. Every other case leaves bit 1 at 0, which already encodes "next = dead".

Lines 28–33 — shift to reveal the result. A second full pass does board[r][c] >>= 1, throwing away the old low bit and dropping the next state into bit 0. The board now holds exactly the next generation.

Complexity → O(m·n) time (two passes, each cell does constant work over 8 neighbors), O(1) extra space — no second grid, just two reserved bits per cell.

INTERVIEWFollow-ups they'll ask

"Why & 1 when counting neighbors?" Because by the time we reach a later cell, earlier cells may already have bit 1 set. Masking with & 1 recovers the original state so the count is correct.
"What if the board is infinite / very large?" Track only live cells in a hash set of (r,c) coordinates and tally neighbor counts in a map; you never materialize empty space.
"Can you do it without bit tricks but still O(1)?" Use sentinel values: e.g. mark a dying live cell as -1 and a newborn dead cell as 2, count with Math.abs(v) === 1, then normalize. Same idea, different encoding.
"What about the edges and corners?" The bounds check nr/nc against 0..rows/colshandles them — border cells simply have fewer neighbors.
"Related to Set Matrix Zeroes?" Yes — both reuse the input itself as scratch storage to hit O(1) space, one via spare bits, the other via marker rows/columns.

OPTIMAL Matrix

gameOfLife.ts
function gameOfLife(board: number[][]): void {
  const rows = board.length;
  const cols = board[0].length;

  // Bit 0 = current state, bit 1 = next state.
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      let live = 0;
      for (let dr = -1; dr <= 1; dr++) {
        for (let dc = -1; dc <= 1; dc++) {
          if (dr === 0 && dc === 0) continue;
          const nr = r + dr, nc = c + dc;
          if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
          live += board[nr][nc] & 1;   // read CURRENT via low bit
        }
      }
      // Rules: live stays/dies, dead may be born. Write next into bit 1.
      if ((board[r][c] & 1) === 1) {
        if (live === 2 || live === 3) board[r][c] |= 2;
      } else if (live === 3) {
        board[r][c] |= 2;
      }
    }
  }

  // Second pass: drop the old state, shift next state down.
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      board[r][c] >>= 1;
    }
  }
}

Complexity → O(m·n) time (two passes, each cell does constant work over 8 neighbors), O(1) extra space — no second grid, just two reserved bits per cell.

ALT 1 Copy the board, read from the copy

O(m·n) time · O(m·n) space

Snapshot the original grid, then compute each cell's next value by reading neighbors from the untouched copy. The simplest correct way to enforce simultaneous updates.

approach-2.ts
function gameOfLife(board: number[][]): void {
  const rows = board.length;
  const cols = board[0].length;
  const prev = board.map((row) => row.slice());

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      let live = 0;
      for (let dr = -1; dr <= 1; dr++) {
        for (let dc = -1; dc <= 1; dc++) {
          if (dr === 0 && dc === 0) continue;
          const nr = r + dr, nc = c + dc;
          if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
          live += prev[nr][nc];
        }
      }
      if (prev[r][c] === 1) {
        board[r][c] = live === 2 || live === 3 ? 1 : 0;
      } else {
        board[r][c] = live === 3 ? 1 : 0;
      }
    }
  }
}

Note → Easiest to reason about because reads always see the original board, but it allocates a second full grid — O(m·n) extra space. The 2-bit encoding stores the next state inside spare bits of the same cell to drop that to O(1).

MNEMONIC The one-liner

"Low bit = now, high bit = next. Count with & 1, set survivors/births with |= 2, then >> 1 everyone."

TRIGGERS When you see _ → reach for _

"update all cells simultaneously"	encode old + new state in one slot
in-place grid update, O(1) space	2-bit encoding (bit0 now, bit1 next)
neighbor read must see original value	mask with value & 1
reveal new state after a full pass	shift every cell value >> 1

SKELETON The reusable shape

skeleton.ts
// Encode next state in bit 1, keep current in bit 0.
for (let r = 0; r < rows; r++)
  for (let c = 0; c < cols; c++) {
    let live = 0;
    // count 8 neighbors using (board[nr][nc] & 1)
    if ((board[r][c] & 1) === 1) {
      if (live === 2 || live === 3) board[r][c] |= 2; // survives
    } else if (live === 3) board[r][c] |= 2;          // born
  }
// Shift everyone down to reveal the next state.
for (let r = 0; r < rows; r++)
  for (let c = 0; c < cols; c++) board[r][c] >>= 1;

FLASHCARDS Tap to flip

Why can’t you just overwrite each cell with its next state?

Updates are simultaneous; an overwritten cell would corrupt the neighbor counts of cells processed later.

tap to flip

1 / 7

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

What is the extra space complexity of the optimal in-place solution?

QUESTION 02

When counting a cell's live neighbors during pass 1, why use board[nr][nc] & 1 instead of board[nr][nc]?

QUESTION 03

A cell holds the value 3 after pass 1. What does that mean?

QUESTION 04

Why is no explicit code needed to handle a live cell that dies?

QUESTION 05

After pass 1, what does the second pass do to every cell?

QUESTION 06

For the board [[0,1,0],[0,0,1],[1,1,1],[0,0,0]], what is the next generation?

QUESTION 07

What is the time complexity of the algorithm?

QUESTION 08

#289 · Game of LifeAdvance Conway's Game of Life one generation in place by stashing the next state in a second bit while the current state stays in bit 0, then shifting every cell right at the end. O(m·n) time, O(1) extra space.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Two states in one integer using two bits

RECIPE Count low bit, write high bit, shift down

COST Complexity & space reduction

RUN IT Encode next state in bit 1, then shift everything down

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL Matrix

ALT 1 Copy the board, read from the copy

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _