Problem Description

The Game of Life is a cellular automaton where you have an m x n grid board. Each cell in the grid has an initial state:

• Live cell: represented by 1
• Dead cell: represented by 0

Each cell interacts with its 8 neighbors (horizontal, vertical, and diagonal) according to these rules:

1. A live cell with fewer than 2 live neighbors dies (under-population)
2. A live cell with 2 or 3 live neighbors survives to the next generation
3. A live cell with more than 3 live neighbors dies (over-population)
4. A dead cell with exactly 3 live neighbors becomes alive (reproduction)

The key challenge is that all cells must be updated simultaneously - meaning the next state is calculated based on the current state of all cells, not on any partially updated states.

Your task is to update the given board in-place to reflect its next state after applying these rules to every cell.

The solution uses an in-place marking technique with temporary states:

• State 2: marks a live cell that will die in the next generation
• State -1: marks a dead cell that will become alive in the next generation

The algorithm works in two passes:

1. First pass: Count live neighbors for each cell and mark cells with temporary states (2 or -1) based on the Game of Life rules
2. Second pass: Convert temporary states to final states (state 2 → 0, state -1 → 1)

This approach allows updating the board in-place while preserving the original state information needed for simultaneous updates.

Intuition

The main challenge in this problem is that all cells need to be updated simultaneously. If we update cells one by one directly (changing 1 to 0 or 0 to 1), we'll lose the original state information that neighboring cells need for their calculations.

For example, if we change a live cell to dead (1 → 0) immediately, when we process its neighbor later, that neighbor won't know this cell was originally alive, leading to an incorrect count of live neighbors.

The key insight is that we need to preserve the original state while marking the future state. We can achieve this by using additional states as temporary markers:

• Instead of directly changing 1 → 0, we mark it as 2 (meaning "currently alive but will die")
• Instead of directly changing 0 → 1, we mark it as -1 (meaning "currently dead but will become alive")

Why these specific values?

• For state 2: It's positive (> 0), so when counting neighbors, we can still recognize it as a currently live cell
• For state -1: It's non-positive (≤ 0), so when counting neighbors, we know it's currently a dead cell

This encoding allows us to:

1. Read the current state: check if board[x][y] > 0 (live) or board[x][y] ≤ 0 (dead)
2. Mark the future state: use 2 and -1 as intermediate values
3. Complete the transition: after all cells are marked, convert 2 → 0 and -1 → 1

This way, we solve the problem in-place with O(1) extra space, while maintaining the simultaneity requirement of the Game of Life rules.

Solution Approach

The solution implements the in-place marking strategy using two passes through the board.

First Pass - Mark Future States:

We iterate through each cell (i, j) in the board:

1. Count live neighbors: For the current cell, we examine all 8 surrounding cells within the grid boundaries. The counting logic uses live = -board[i][j] initially to exclude the current cell from its own neighbor count, then adds 1 for each neighbor where board[x][y] > 0 (currently alive).

2. Apply Game of Life rules with marking:

   • If the current cell is alive (board[i][j] == 1) and has fewer than 2 or more than 3 live neighbors (live < 2 or live > 3), mark it as 2 (will die)
   • If the current cell is dead (board[i][j] == 0) and has exactly 3 live neighbors (live == 3), mark it as -1 (will become alive)
   • Cells that don't meet these conditions remain unchanged (live cells with 2-3 neighbors stay 1, dead cells without exactly 3 neighbors stay 0)

Second Pass - Finalize States:

After all cells have been marked, we traverse the board again:

• Convert state 2 (alive but dying) to 0 (dead)
• Convert state -1 (dead but becoming alive) to 1 (alive)
• States 0 and 1 remain as they are

Implementation Details:

# First pass: mark transitions
for i in range(m):
    for j in range(n):
        live = -board[i][j]  # Start with negative current cell value
        # Check all 8 neighbors
        for x in range(i - 1, i + 2):
            for y in range(j - 1, j + 2):
                if 0 <= x < m and 0 <= y < n and board[x][y] > 0:
                    live += 1
      
        # Apply rules with marking
        if board[i][j] and (live < 2 or live > 3):
            board[i][j] = 2  # Live cell dies
        if board[i][j] == 0 and live == 3:
            board[i][j] = -1  # Dead cell becomes alive

# Second pass: finalize states
for i in range(m):
    for j in range(n):
        if board[i][j] == 2:
            board[i][j] = 0
        elif board[i][j] == -1:
            board[i][j] = 1

This approach achieves O(mn) time complexity with two passes through the board and O(1) space complexity by modifying the board in-place.

Example Walkthrough

Let's walk through a small 3x3 grid to illustrate how the solution works:

Initial Board:

[1, 1, 0]
[1, 0, 0]
[0, 1, 0]

First Pass - Mark Future States:

Processing cell (0,0) with value 1:

• Count live neighbors: Check all 8 directions (only 3 are in bounds)
  • (0,1) = 1 ✓, (1,0) = 1 ✓, (1,1) = 0
  • Total live neighbors = 2
• Apply rules: Live cell with 2 neighbors survives → Keep as 1

Processing cell (0,1) with value 1:

• Count live neighbors:
  • (0,0) = 1 ✓, (0,2) = 0, (1,0) = 1 ✓, (1,1) = 0, (1,2) = 0
  • Total live neighbors = 2
• Apply rules: Live cell with 2 neighbors survives → Keep as 1

Processing cell (0,2) with value 0:

• Count live neighbors:
  • (0,1) = 1 ✓, (1,1) = 0, (1,2) = 0
  • Total live neighbors = 1
• Apply rules: Dead cell with 1 neighbor stays dead → Keep as 0

Processing cell (1,0) with value 1:

• Count live neighbors:
  • (0,0) = 1 ✓, (0,1) = 1 ✓, (1,1) = 0, (2,0) = 0, (2,1) = 1 ✓
  • Total live neighbors = 3
• Apply rules: Live cell with 3 neighbors survives → Keep as 1

Processing cell (1,1) with value 0:

• Count live neighbors:
  • All 8 neighbors: (0,0)=1 ✓, (0,1)=1 ✓, (0,2)=0, (1,0)=1 ✓, (1,2)=0, (2,0)=0, (2,1)=1 ✓, (2,2)=0
  • Total live neighbors = 4
• Apply rules: Dead cell with 4 neighbors stays dead → Keep as 0

Processing cell (1,2) with value 0:

• Count live neighbors:
  • (0,1) = 1 ✓, (0,2) = 0, (1,1) = 0, (2,1) = 1 ✓, (2,2) = 0
  • Total live neighbors = 2
• Apply rules: Dead cell with 2 neighbors stays dead → Keep as 0

Processing cell (2,0) with value 0:

• Count live neighbors:
  • (1,0) = 1 ✓, (1,1) = 0, (2,1) = 1 ✓
  • Total live neighbors = 2
• Apply rules: Dead cell with 2 neighbors stays dead → Keep as 0

Processing cell (2,1) with value 1:

• Count live neighbors:
  • (1,0) = 1 ✓, (1,1) = 0, (1,2) = 0, (2,0) = 0, (2,2) = 0
  • Total live neighbors = 1
• Apply rules: Live cell with 1 neighbor dies (under-population) → Mark as 2

Processing cell (2,2) with value 0:

• Count live neighbors:
  • (1,1) = 0, (1,2) = 0, (2,1) = 1 ✓ (still counted as 1 even though marked as 2)
  • Total live neighbors = 1
• Apply rules: Dead cell with 1 neighbor stays dead → Keep as 0

Board After First Pass:

[1, 1, 0]
[1, 0, 0]
[0, 2, 0]  // Cell (2,1) marked as 2 (will die)

Second Pass - Finalize States:

Convert all temporary states:

• Cell (2,1): 2 → 0 (dying cell becomes dead)
• All other cells remain unchanged

Final Board:

[1, 1, 0]
[1, 0, 0]
[0, 0, 0]

The key insight demonstrated here is how marking cell (2,1) as 2 preserves its "currently alive" status when cell (2,2) counts its neighbors later, ensuring the simultaneous update requirement is met.

Solution Implementation

Time and Space Complexity

The time complexity is O(m × n), where m and n are the number of rows and columns of the board, respectively. The algorithm consists of two main phases:

1. First nested loop: iterates through all m × n cells, and for each cell, it checks at most 9 neighboring positions (including itself). Since the neighbor checking is bounded by a constant (9), this phase takes O(m × n) time.
2. Second nested loop: iterates through all m × n cells again to update the encoded values back to their final states, taking O(m × n) time.

Therefore, the overall time complexity is O(m × n) + O(m × n) = O(m × n).

The space complexity is O(1). The algorithm modifies the board in-place using an encoding scheme where:

• 2 represents a cell that was alive but will become dead
• -1 represents a cell that was dead but will become alive
• 1 represents a currently alive cell
• 0 represents a currently dead cell

No additional data structures are used that scale with the input size. Only a constant amount of extra space is used for variables like m, n, i, j, x, y, and live.

Common Pitfalls

1. Incorrect Neighbor Counting Logic

Pitfall: A common mistake is incorrectly initializing the live neighbor count. The code uses live = -board[i][j] to exclude the current cell from its own neighbor count, but developers often forget this adjustment and simply start with live = 0, leading to off-by-one errors.

Why it happens: When iterating through the 3x3 grid centered on a cell, the iteration includes the cell itself. If the current cell is alive (value = 1), it would incorrectly count itself as a neighbor.

Incorrect approach:

live = 0  # Wrong: will count the current cell if it's alive
for x in range(i - 1, i + 2):
    for y in range(j - 1, j + 2):
        if 0 <= x < m and 0 <= y < n and board[x][y] > 0:
            live += 1

Correct solution:

# Method 1: Start with negative current cell value
live = -board[i][j]
for x in range(i - 1, i + 2):
    for y in range(j - 1, j + 2):
        if 0 <= x < m and 0 <= y < n and board[x][y] > 0:
            live += 1

# Method 2: Skip the current cell explicitly
live = 0
for x in range(i - 1, i + 2):
    for y in range(j - 1, j + 2):
        if x == i and y == j:
            continue  # Skip the current cell
        if 0 <= x < m and 0 <= y < n and board[x][y] > 0:
            live += 1

2. Misunderstanding State Encoding During Neighbor Counting

Pitfall: Using the wrong condition to check if a neighbor is currently alive. The code checks board[x][y] > 0 to determine if a cell is currently alive (states 1 or 2), but developers might mistakenly use board[x][y] == 1 or board[x][y] != 0.

Why it matters:

• State 2 represents a cell that is currently alive but will die
• State -1 represents a cell that is currently dead but will become alive
• During the first pass, we need to count based on the current state, not the future state

Incorrect approaches:

# Wrong: Misses cells marked as state 2 (currently alive, will die)
if board[x][y] == 1:
    live += 1

# Wrong: Counts state -1 cells as alive (they're currently dead)
if board[x][y] != 0:
    live += 1

Correct solution:

# Correct: Counts both state 1 and state 2 as currently alive
if board[x][y] > 0:
    live += 1

3. Modifying the Wrong Cells in the First Pass

Pitfall: Forgetting to check the current state before applying transitions, leading to overwriting already-marked cells.

Example mistake:

# Wrong: Overwrites state 2 with -1 if it happens to have 3 live neighbors
if live == 3:
    board[i][j] = -1  # Should only apply to dead cells!

Correct solution:

# Check current state before marking transitions
if board[i][j] == 1 and (live < 2 or live > 3):
    board[i][j] = 2  # Only mark live cells for death
if board[i][j] == 0 and live == 3:
    board[i][j] = -1  # Only mark dead cells for birth

4. Boundary Check Errors

Pitfall: Forgetting to check grid boundaries when examining neighbors, causing index out of bounds errors.

Incorrect approach:

# Wrong: No boundary checking
for x in range(i - 1, i + 2):
    for y in range(j - 1, j + 2):
        if board[x][y] > 0:  # IndexError for edge cells!
            live += 1

Correct solution:

# Always check boundaries before accessing array elements
for x in range(i - 1, i + 2):
    for y in range(j - 1, j + 2):
        if 0 <= x < m and 0 <= y < n and board[x][y] > 0:
            live += 1