Game of Life

Q: What is the time complexity of Game of Life?

O(m * n). Each cell is visited twice: once to compute neighbor counts and mark transitions, and once to finalize states. Each neighbor check is constant time (8 directions), so total time is proportional to the number of cells.

Q: What pattern does Game of Life use?

The Pattern: Matrix Traversal (In-Place State Encoding) The Heuristic: When simultaneous updates depend on neighbors' original states, encode transitions with temporary markers that preserve original information during traversal, enabling in-place updates without extra space.

Medium Matrix

Problem

Given a 2D board representing the current state of cells (1 for live, 0 for dead), update the board to the next state according to the Game of Life rules simultaneously for all cells.

m == board.length
n == board[i].length
1 ≤ m, n ≤ 25
board[i][j] is 0 or 1

Example

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]]

Starting with the given board, the algorithm counts live neighbors for each cell. For example, the cell at (1,0) is dead but has exactly three live neighbors, so it becomes live (value 1). The cell at (0,1) is live but has only one live neighbor, so it dies (value 0). The algorithm uses temporary markers (-1 for live-to-dead, 2 for dead-to-live) to track transitions without affecting neighbor counts. After processing all cells, it finalizes the board by converting temporary markers to their final states.

Approach

Straightforward Solution

A naive approach would create a copy of the board to compute the next state, then copy it back. This uses O(m*n) extra space, which is inefficient for large boards.

Core Observation

The next state of each cell depends on the count of live neighbors, but all updates must happen simultaneously. This means the algorithm cannot update the board in-place naively, as changes would affect neighbor counts of other cells.

Path to Optimal

The key insight is to encode state transitions in-place using temporary markers that distinguish between original and next states. For example, marking live-to-dead cells as -1 and dead-to-live cells as 2 allows counting neighbors by checking the absolute value, preserving original states during neighbor counting. After processing, a final pass converts these markers to their final states.

Optimal Approach

Traverse each cell, count live neighbors by checking all eight directions and considering cells with absolute value 1 as originally live. Apply the rules and mark transitions with temporary values (-1 for live-to-dead, 2 for dead-to-live). Finally, traverse the board again to finalize states by converting positive values to 1 and others to 0. This achieves O(m*n) time and O(1) auxiliary space.

Time

O(m * n)

Each cell is visited twice: once to compute neighbor counts and mark transitions, and once to finalize states. Each neighbor check is constant time (8 directions), so total time is proportional to the number of cells.

Space

O(1)

The algorithm uses only a fixed set of temporary markers and a constant-size directions array, modifying the board in-place without additional data structures proportional to input size.

Pattern Spotlight

Matrix Traversal (In-Place State Encoding)

When simultaneous updates depend on neighbors' original states, encode transitions with temporary markers that preserve original information during traversal, enabling in-place updates without extra space.

Solution

1class Solution:
  def gameOfLife(self, board: List[List[int]]) -> None:
      rows = len(board)
      cols = len(board[0])
5
      directions = [
          (-1, -1), (-1, 0), (-1, 1),
          (0, -1),          (0, 1),
          (1, -1),  (1, 0), (1, 1)
      ]
11
      for r in range(rows):
          for c in range(cols):
              live_neighbors = 0
15
              for dr, dc in directions:
                  nr = r + dr
                  nc = c + dc
19
                  if 0 <= nr < rows and 0 <= nc < cols and abs(board[nr][nc]) == 1:
                      live_neighbors += 1
22
              if board[r][c] == 1 and (live_neighbors < 2 or live_neighbors > 3):
                  board[r][c] = -1
25
              if board[r][c] == 0 and live_neighbors == 3:
                  board[r][c] = 2
28
      for r in range(rows):
          for c in range(cols):
              if board[r][c] > 0:
                  board[r][c] = 1
              else:
                  board[r][c] = 0

Step-by-Step Solution

Count Live Neighbors and Mark State Transitions In-Place

3rows = len(board)
4cols = len(board[0])
6directions = [
  (-1, -1), (-1, 0), (-1, 1),
  (0, -1),          (0, 1),
  (1, -1),  (1, 0), (1, 1)
12for r in range(rows):
  for c in range(cols):
      live_neighbors = 0
      for dr, dc in directions:
          nr = r + dr
          nc = c + dc
          if 0 <= nr < rows and 0 <= nc < cols and abs(board[nr][nc]) == 1:
              live_neighbors += 1
      if board[r][c] == 1 and (live_neighbors < 2 or live_neighbors > 3):
          board[r][c] = -1
      if board[r][c] == 0 and live_neighbors == 3:
          board[r][c] = 2

Objective

To iterate over each cell, count its live neighbors considering original states, and mark cells with temporary values to indicate state changes without losing original information.

Key Insight

Using the absolute value of cell states allows the algorithm to distinguish originally live cells (abs == 1) from dead ones, even after marking transitions. This enables accurate neighbor counts while performing in-place updates. Marking live-to-dead as -1 and dead-to-live as 2 encodes transitions without interfering with neighbor calculations.

Interview Quick-Check

Core Logic

Count live neighbors by checking all eight directions and using abs(board[nr][nc]) == 1 to identify originally live cells, ensuring neighbor counts remain accurate despite in-place updates.

State & Boundaries

Check boundary conditions for neighbors (0 <= nr < rows and 0 <= nc < cols) to avoid index errors.

Common Pitfalls & Bugs

Failing to use absolute values when counting neighbors leads to incorrect counts because temporary markers (-1, 2) would be misinterpreted.

Complexity

This step runs in O(m*n) time, with a constant factor of 8 for neighbor checks, which is efficient for the problem constraints.

Finalize Board by Converting Temporary Markers to Final States

29for r in range(rows):
  for c in range(cols):
      if board[r][c] > 0:
          board[r][c] = 1
      else:
          board[r][c] = 0

Objective

To traverse the board again and convert all temporary markers to their final live or dead states, completing the simultaneous update.

Key Insight

Cells marked with positive values (1 or 2) represent live cells in the next state, while zero or negative values represent dead cells. This final pass cleans up the board, ensuring all cells reflect the correct next state after the in-place transition encoding.

Interview Quick-Check

Core Logic

Convert all cells with values greater than 0 to 1 (live) and all others to 0 (dead) to finalize the next state.

State & Boundaries

Iterate over all rows and columns to ensure every cell is updated.

Common Pitfalls & Bugs

Forgetting to finalize the board leaves temporary markers, causing incorrect output.

Complexity

This step is O(m*n) time and O(1) auxiliary space, maintaining overall efficiency.

Line Analysis

This solution has 3 Critical lines interviewers watch for.

Line 20 Critical

if 0 <= nr < rows and 0 <= nc < cols and abs(board[nr][nc]) == 1:

Check if neighbor is within board boundaries and originally live.

This condition is critical because it preserves the original state information during in-place updates, enabling accurate neighbor counts even when cells have been marked for state changes.

Line 23 Critical

if board[r][c] == 1 and (live_neighbors < 2 or live_neighbors > 3):

Mark live cells that die due to underpopulation or overpopulation.

Marking with -1 allows the algorithm to distinguish cells that were originally live but will die, preserving original state information for neighbor counts while encoding the next state.

Line 26 Critical

if board[r][c] == 0 and live_neighbors == 3:

Mark dead cells that become live due to reproduction.

Marking with 2 allows the algorithm to distinguish cells that were originally dead but will become live, enabling simultaneous updates without corrupting neighbor counts.

Line 24 Core

board[r][c] = -1

Apply the live-to-dead marker to the current cell.

This in-place update encodes the state transition while preserving original information for simultaneous updates.

Line 27 Core

board[r][c] = 2

Apply the dead-to-live marker to the current cell.

This in-place update encodes the state transition while preserving original information for simultaneous updates.

Line 6 Core

directions = [

Define the eight possible neighbor directions around a cell.

Enumerating all eight directions (horizontal, vertical, diagonal) allows systematic neighbor counting for each cell, which is central to applying the Game of Life rules.

Line 16 Core

for dr, dc in directions:

Iterate over each neighbor direction.

This loop systematically checks all eight neighbors for the current cell to count live neighbors.

Line 21 Core

live_neighbors += 1

Increment the live neighbor count for the current cell.

Accurately counting live neighbors is the foundation for applying the Game of Life rules to determine the next state.

Line 31 Core

if board[r][c] > 0:

Check if the current cell is live or marked to become live.

Cells with positive values (1 or 2) represent live cells in the next state, so they must be set to 1.

Line 33 Core

else:

Handle cells that are dead or marked to become dead.

Cells with zero or negative values represent dead cells in the next state and must be set to 0.

Line 14 Standard

live_neighbors = 0

Initialize the count of live neighbors for the current cell.

Resetting the live neighbor count for each cell is necessary before counting neighbors to apply the Game of Life rules correctly.

Line 17 Standard

nr = r + dr

Calculate the neighbor's row index.

Computing neighbor coordinates is essential for accessing neighbor cells and performing boundary checks.

Line 18 Standard

nc = c + dc

Calculate the neighbor's column index.

Computing neighbor coordinates is essential for accessing neighbor cells and performing boundary checks.

Line 32 Standard

board[r][c] = 1

Set the current cell to live state (1).

Finalizing live cells ensures the board correctly reflects the next state after all transitions.

Line 34 Standard

board[r][c] = 0

Set the current cell to dead state (0).

Finalizing dead cells completes the in-place update of the board to the next state.

Line 7 Standard

(-1, -1), (-1, 0), (-1, 1),

List the first three neighbor directions (top-left, top, top-right).

These directions cover the upper neighbors, which must be checked to count live neighbors accurately.

Line 8 Standard

(0, -1),          (0, 1),

List the middle two neighbor directions (left, right).

These directions cover the horizontal neighbors, completing the neighbor set.

Line 9 Standard

(1, -1),  (1, 0), (1, 1)

List the last three neighbor directions (bottom-left, bottom, bottom-right).

These directions cover the lower neighbors, ensuring all eight neighbors are considered.

Line 12 Standard

for r in range(rows):

Iterate over each row of the board.

This outer loop ensures every cell in the board is processed for neighbor counting and state transition marking.

Line 13 Standard

for c in range(cols):

Iterate over each column of the current row.

This inner loop completes the traversal of every cell in the board.

Line 29 Standard

for r in range(rows):

Iterate over each row to finalize the board.

This loop prepares to convert temporary markers to final states, completing the simultaneous update process.

Line 30 Standard

for c in range(cols):

Iterate over each column of the current row to finalize the board.

This inner loop ensures every cell is updated to its final state.

Line 3 Basic

rows = len(board)

Calculate the number of rows in the board.

Knowing the number of rows is essential for boundary checks during neighbor traversal and for iterating over the board.

Line 4 Basic

cols = len(board[0])

Calculate the number of columns in the board.

Knowing the number of columns is essential for boundary checks during neighbor traversal and for iterating over the board.

Test Your Understanding

Why does the algorithm use temporary markers like -1 and 2 instead of directly updating cells to 0 or 1 during the first pass?

Because updating cells directly would alter the original states needed to count live neighbors correctly for other cells. Temporary markers preserve the original state information while indicating the next state, allowing simultaneous updates without corrupting neighbor counts.

Don't just read it. Drill it.

Reconstruct Game of Life from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Game of Life drill

or drill a free problem

1	`class Solution:`
2	`def gameOfLife(self, board: List[List[int]]) -> None:`
3	`rows = len(board)`
4	`cols = len(board[0])`
5
6	`directions = [`
7	`(-1, -1), (-1, 0), (-1, 1),`
8	`(0, -1), (0, 1),`
9	`(1, -1), (1, 0), (1, 1)`
10	`]`
11
12	`for r in range(rows):`
13	`for c in range(cols):`
14	`live_neighbors = 0`
15
16	`for dr, dc in directions:`
17	`nr = r + dr`
18	`nc = c + dc`
19
20	`if 0 <= nr < rows and 0 <= nc < cols and abs(board[nr][nc]) == 1:`
21	`live_neighbors += 1`
22
23	`if board[r][c] == 1 and (live_neighbors < 2 or live_neighbors > 3):`
24	`board[r][c] = -1`
25
26	`if board[r][c] == 0 and live_neighbors == 3:`
27	`board[r][c] = 2`
28
29	`for r in range(rows):`
30	`for c in range(cols):`
31	`if board[r][c] > 0:`
32	`board[r][c] = 1`
33	`else:`
34	`board[r][c] = 0`

3	`rows = len(board)`
4	`cols = len(board[0])`
6	`directions = [`
7	`(-1, -1), (-1, 0), (-1, 1),`
8	`(0, -1), (0, 1),`
9	`(1, -1), (1, 0), (1, 1)`
12	`for r in range(rows):`
13	`for c in range(cols):`
14	`live_neighbors = 0`
16	`for dr, dc in directions:`
17	`nr = r + dr`
18	`nc = c + dc`
20	`if 0 <= nr < rows and 0 <= nc < cols and abs(board[nr][nc]) == 1:`
21	`live_neighbors += 1`
23	`if board[r][c] == 1 and (live_neighbors < 2 or live_neighbors > 3):`
24	`board[r][c] = -1`
26	`if board[r][c] == 0 and live_neighbors == 3:`
27	`board[r][c] = 2`