Game of Life (Encode States In-Place)

▶

Steps

setup

Initialize board dimensions and directions

We determine the number of rows (m) and columns (n) and define the 8 directions to check neighbors around each cell.

💡 Knowing board size and neighbor directions sets up the traversal and neighbor counting logic.

Line:

m, n = len(board), len(board[0])
directions = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]

💡 The algorithm will iterate over each cell using these dimensions and check neighbors using these directions.

traverse

Start processing cell (0,0)

Begin with the top-left cell at row 0, column 0 to count its live neighbors.

💡 Processing each cell one by one is essential to apply the Game of Life rules correctly.

Line:

for i in range(m):
    for j in range(n):

💡 The outer loops control which cell is currently being evaluated.

compare

Count live neighbors of cell (0,0)

Check each of the 8 directions around cell (0,0) to count how many neighbors are alive (state 1 or 2).

💡 Counting live neighbors determines the next state of the cell according to the rules.

Line:

for dx, dy in directions:
    x, y = i + dx, j + dy
    if 0 <= x < m and 0 <= y < n and board[x][y] in (1, 2):
        live_neighbors += 1

💡 Neighbors outside the board are ignored; only live neighbors count.

insert

Decide next state for cell (0,0)

Cell (0,0) is dead (0) and has 1 live neighbor, so it remains dead; no state change encoded.

💡 Only cells with exactly 3 live neighbors become live; others stay the same.

Line:

if board[i][j] == 1:
    if live_neighbors < 2 or live_neighbors > 3:
        board[i][j] = 2
else:
    if live_neighbors == 3:
        board[i][j] = 3

💡 Dead cells only become live if they have exactly 3 live neighbors.

compare

Process cell (0,1) - count live neighbors

Move to cell (0,1), which is live (1). Count its live neighbors by checking all directions.

💡 Live cells may die or survive depending on neighbors; counting is crucial.

Line:

live_neighbors = 0
for dx, dy in directions:
    x, y = i + dx, j + dy
    if 0 <= x < m and 0 <= y < n and board[x][y] in (1, 2):
        live_neighbors += 1

💡 Counting neighbors includes cells marked 2 (live->dead) as still alive for counting.

insert

Decide next state for cell (0,1)

Cell (0,1) has 1 live neighbor, which is less than 2, so it will die; encode as 2 (live->dead).

💡 Encoding state 2 marks cells that were live but will die, preserving original info for neighbor counts.

Line:

if board[i][j] == 1:
    if live_neighbors < 2 or live_neighbors > 3:
        board[i][j] = 2

💡 Encoding allows in-place update without losing original state information.

compare

Process cell (1,0) - count live neighbors

At cell (1,0), which is dead (0), count live neighbors to check if it becomes live.

💡 Dead cells with exactly 3 live neighbors become live; counting neighbors is key.

Line:

live_neighbors = 0
for dx, dy in directions:
    x, y = i + dx, j + dy
    if 0 <= x < m and 0 <= y < n and board[x][y] in (1, 2):
        live_neighbors += 1

💡 Neighbors marked 2 are still considered live for counting.

insert

Encode cell (1,0) as dead->live

Cell (1,0) has exactly 3 live neighbors, so it becomes live; encode as 3 (dead->live).

💡 Encoding state 3 marks cells that were dead but will become live, preserving original info.

Line:

else:
    if live_neighbors == 3:
        board[i][j] = 3

💡 Encoding allows updating the board in-place without losing original states needed for neighbor counts.

traverse

Finish first pass: encode all transitions

Continue processing all cells similarly, encoding live->dead as 2 and dead->live as 3.

💡 This pass encodes all state changes in-place, preserving original states for neighbor counts.

Line:

for i in range(m):
    for j in range(n):
        # count neighbors and encode transitions

💡 After this pass, the board contains original and encoded states mixed.

traverse

Start second pass to finalize states

Traverse the board again to convert encoded states 2 and 3 back to final states 0 and 1.

💡 This pass completes the in-place update by finalizing all cell states.

Line:

for i in range(m):
    for j in range(n):
        if board[i][j] == 2:
            board[i][j] = 0
        elif board[i][j] == 3:
            board[i][j] = 1

💡 Encoded states are temporary markers; final states are restored here.

shrink

Finalize cell (0,1) from 2 to 0

Cell (0,1) was encoded as 2 (live->dead), now converted to 0 (dead).

💡 This step completes the transition for this cell.

Line:

if board[i][j] == 2:
    board[i][j] = 0

💡 Final states reflect the next generation of the board.

shrink

Finalize cell (1,0) from 3 to 1

Cell (1,0) was encoded as 3 (dead->live), now converted to 1 (live).

💡 This step completes the transition for this cell.

Line:

elif board[i][j] == 3:
    board[i][j] = 1

💡 Final states reflect the next generation of the board.

shrink

Finalize remaining encoded cells

Continue converting all 2s to 0s and 3s to 1s to complete the board update.

💡 This finalizes the entire board to the next generation state.

Line:

for i in range(m):
    for j in range(n):
        if board[i][j] == 2:
            board[i][j] = 0
        elif board[i][j] == 3:
            board[i][j] = 1

💡 The board now fully represents the next state of the Game of Life.

reconstruct

Final board state after all updates

The board now shows the next generation states with all transitions applied in-place.

💡 This final state is the output of the Game of Life update.

Line:

print(board)

💡 The in-place encoding and decoding successfully updated the board without extra space.

def gameOfLife(board):
    m, n = len(board), len(board[0])  # STEP 1
    directions = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]  # STEP 1
    for i in range(m):  # STEP 2
        for j in range(n):  # STEP 2
            live_neighbors = 0  # STEP 3
            for dx, dy in directions:  # STEP 3
                x, y = i + dx, j + dy  # STEP 3
                if 0 <= x < m and 0 <= y < n and board[x][y] in (1, 2):  # STEP 3
                    live_neighbors += 1  # STEP 3
            if board[i][j] == 1:  # STEP 4,6
                if live_neighbors < 2 or live_neighbors > 3:  # STEP 4,6
                    board[i][j] = 2  # live->dead encoding  # STEP 6
            else:  # STEP 4,8
                if live_neighbors == 3:  # STEP 8
                    board[i][j] = 3  # dead->live encoding  # STEP 8
    for i in range(m):  # STEP 10
        for j in range(n):  # STEP 10
            if board[i][j] == 2:  # STEP 11
                board[i][j] = 0  # finalize live->dead  # STEP 11
            elif board[i][j] == 3:  # STEP 12
                board[i][j] = 1  # finalize dead->live  # STEP 12

📊

Game of Life (Encode States In-Place) - Watch the Algorithm Execute, Step by Step

Watching this step-by-step helps you understand how the algorithm cleverly encodes state changes without extra space, which is hard to grasp from code alone.

setup

j

0

1

2

3

traverse

j

0

1

2

3

compare

j

0

dx/dy

1

2

3

Result: 1

insert

j

0

1

2

3

compare

i

0

j

1

dx/dy

2

3

Result: 1

insert

i

0

j

1

2

3

compare

j

0

i

1

2

dx/dy

3

Result: 3

insert

j

0

i

1

2

3

traverse

0

j

1

2

i

3

traverse

j

0

1

2

3

shrink

i

0

j

1

2

3

shrink

j

0

i

1

2

3

shrink

0

1

j

2

i

3

record

0

1

2

3

Result: [[0,0,0],[1,0,1],[0,1,1],[0,1,0]]

Key Takeaways

✓ In-place encoding with states 2 and 3 allows updating the board without extra space.

This insight is hard to see from code alone because the temporary states look confusing without visualization.

✓ Counting neighbors includes cells marked 2 (live->dead) to preserve original state during the first pass.

Understanding this prevents confusion about why some cells still count as live even after being marked for death.

✓ The final pass converts encoded states back to 0 or 1, completing the update cleanly.

Seeing this step visually clarifies how the algorithm finalizes the board after encoding transitions.

Practice

1. Given the following code for maximum hourglass sum using sliding window, what is the value of max_sum after processing the first row (i=0) of the matrix below? Matrix: [[1, 1, 1, 0], [0, 1, 0, 0], [1, 1, 1, 0]]

def max_hourglass_sum_sliding(matrix):
    n = len(matrix)
    m = len(matrix[0])
    max_sum = float('-inf')

    for i in range(n - 2):
        current_sum = (matrix[i][0] + matrix[i][1] + matrix[i][2] +
                       matrix[i+1][1] +
                       matrix[i+2][0] + matrix[i+2][1] + matrix[i+2][2])
        if current_sum > max_sum:
            max_sum = current_sum

        for j in range(1, m - 2):
            current_sum -= (matrix[i][j-1] + matrix[i+1][j] + matrix[i+2][j-1])
            current_sum += (matrix[i][j+2] + matrix[i+1][j+1] + matrix[i+2][j+2])
            if current_sum > max_sum:
                max_sum = current_sum
    return max_sum

easy

A. 7

B. 8

C. 6

D. 9

Solution

1. Step 1: Calculate initial hourglass sum at i=0, j=0

   Sum = 1+1+1 + 1 + 1+1+1 = 7

2. Step 2: Check sliding window for j=1 (only one possible)

   Subtract left column: 1 + 1 + 1 = 3; Add right column: 0 + 0 + 0 = 0; New sum = 7 - 3 + 0 = 4; max_sum remains 7

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Initial sum 7 is max after first row [OK]

Hint: Initial hourglass sum sets max before sliding [OK]

Common Mistakes:

• Off-by-one in sliding window update
• Forgetting to update max_sum after sliding
• Misindexing matrix elements

2. Consider the following Python code snippet for validating a Sudoku board using bitmasking:

def isValidSudoku(board):
    rows = [0] * 9
    cols = [0] * 9
    boxes = [0] * 9
    for i in range(9):
        for j in range(9):
            if board[i][j] == '.':
                continue
            val = ord(board[i][j]) - ord('1')
            mask = 1 << val
            box_index = (i // 3) * 3 + (j // 3)
            if (rows[i] & mask) or (cols[j] & mask) or (boxes[box_index] & mask):
                return false
            rows[i] |= mask
            cols[j] |= mask
            boxes[box_index] |= mask
    return true

board = [
    ['5','3','.','.','7','.','.','.','.'],
    ['6','.','.','1','9','5','.','.','.'],
    ['.','9','8','.','.','.','.','6','.'],
    ['8','.','.','.','6','.','.','.','3'],
    ['4','.','.','8','.','3','.','.','1'],
    ['7','.','.','.','2','.','.','.','6'],
    ['.','6','.','.','.','.','2','8','.'],
    ['.','.','.','4','1','9','.','.','5'],
    ['.','.','.','.','8','.','.','7','9']
]

print(isValidSudoku(board))

What is the output of this code?

easy

A. true

B. false

C. Raises an exception due to invalid indexing

D. Returns null

Solution

1. Step 1: Trace first few iterations

   All digits are unique in their rows, columns, and boxes; no mask conflicts occur.

2. Step 2: Confirm no duplicates found

   Since no duplicates are detected, the function completes and returns true.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Standard valid Sudoku board returns true [OK]

Hint: No duplicates -> function returns true [OK]

Common Mistakes:

• Misreading box index calculation
• Assuming '.' causes errors
• Confusing return values

3. Consider the following buggy code for maximum hourglass sum using sliding window. Which line contains the subtle bug that can cause incorrect results when all matrix values are negative?

def max_hourglass_sum_sliding(matrix):
    n = len(matrix)
    m = len(matrix[0])
    max_sum = 0  # Bug here

    for i in range(n - 2):
        current_sum = (matrix[i][0] + matrix[i][1] + matrix[i][2] +
                       matrix[i+1][1] +
                       matrix[i+2][0] + matrix[i+2][1] + matrix[i+2][2])
        if current_sum > max_sum:
            max_sum = current_sum

        for j in range(1, m - 2):
            current_sum -= (matrix[i][j-1] + matrix[i+1][j] + matrix[i+2][j-1])
            current_sum += (matrix[i][j+2] + matrix[i+1][j+1] + matrix[i+2][j+2])
            if current_sum > max_sum:
                max_sum = current_sum
    return max_sum

medium

A. Line initializing max_sum to 0

B. Line computing current_sum for initial hourglass

C. Line subtracting left column elements in sliding window

D. Line adding right column elements in sliding window

Solution

1. Step 1: Understand initialization of max_sum

   Setting max_sum = 0 causes incorrect max when all values are negative, as max_sum never updates to negative sums.

2. Step 2: Confirm other lines are correct

   Current_sum calculation and sliding window updates are correct; bug is only in initialization.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Proper initialization must be -inf to handle negative values [OK]

Hint: Initialize max_sum to -inf to handle negative values [OK]

Common Mistakes:

• Initializing max_sum to 0
• Misindexing sliding window updates
• Forgetting to update max_sum after sliding

4. Consider this buggy version of the optimal Set Matrix Zeroes code. Which line contains the subtle bug that causes incorrect zeroing in some cases?

def setZeroes(matrix):
    m, n = len(matrix), len(matrix[0])
    first_row_zero = any(matrix[0][j] == 0 for j in range(n))
    first_col_zero = any(matrix[i][0] == 0 for i in range(m))
    for i in range(m):  # Bug here: starts from 0 instead of 1
        for j in range(n):
            if matrix[i][j] == 0:
                matrix[i][0] = 0
                matrix[0][j] = 0
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][0] == 0 or matrix[0][j] == 0:
                matrix[i][j] = 0
    if first_row_zero:
        for j in range(n):
            matrix[0][j] = 0
    if first_col_zero:
        for i in range(m):
            matrix[i][0] = 0

medium

A. Line with 'for i in range(m):' (marking zeros in first pass)

B. Line with 'first_row_zero = any(matrix[0][j] == 0 for j in range(n))'

C. Line with 'first_col_zero = any(matrix[i][0] == 0 for i in range(m))'

D. Line with 'for i in range(1, m):' (zeroing based on flags)

Solution

1. Step 1: Identify marking loop range

   The marking loop should start from 1 to avoid overwriting first row/column flags prematurely.

2. Step 2: Understand impact

   Starting from 0 causes first row/column to be overwritten before flags are saved, losing zero info.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing loop to start at 1 fixes the bug [OK]

Hint: Mark zeros starting from index 1 to preserve flags [OK]

Common Mistakes:

• Zeroing first row/column too early
• Incorrect loop ranges causing info loss
• Confusing first pass marking with zeroing pass

5. Identify the bug in the following code that attempts to transpose a square matrix in-place:

def transpose(matrix):
    n = len(matrix)
    for i in range(n):
        for j in range(n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

What is the issue?

medium

A. The inner loop should start from j = i + 1 to avoid swapping elements twice.

B. The outer loop should start from i = 1 instead of 0.

C. The swap operation should use a temporary variable instead of tuple unpacking.

D. The function should return the matrix after transposition.

Solution

1. Step 1: Analyze loop ranges

   Both loops run from 0 to n-1, causing each pair to be swapped twice, reverting to original matrix.

2. Step 2: Correct loop bounds

   Starting inner loop from j = i + 1 ensures each pair is swapped only once, fixing the bug.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Swapping twice cancels changes, so adjusting inner loop start fixes it [OK]

Hint: Swap only upper triangle elements once [OK]

Common Mistakes:

• Swapping entire matrix causing double swaps
• Incorrect loop bounds leading to index errors
• Unnecessary return statements