Spiral Matrix II (Fill Outward Spiral)

▶

Steps

setup

Initialize matrix and boundaries

Create a 3x3 matrix filled with zeros. Set top, bottom, left, and right boundaries to cover the whole matrix. Initialize the number to fill as 1 and direction as right (0).

💡 Setting up boundaries and direction prepares the algorithm to fill the matrix layer by layer in a spiral.

Line:

matrix = [[0]*n for _ in range(n)]
top, bottom = 0, n - 1
left, right = 0, n - 1
num = 1
direction = 0

💡 Boundaries define the current layer to fill; direction controls movement.

fill_row

Fill top row moving right

Fill the top row from left to right with numbers 1, 2, and 3. Increment num after each fill.

💡 Filling the top row first sets the outermost layer of the spiral.

Line:

for col in range(left, right + 1):
    matrix[top][col] = num
    num += 1
top += 1

💡 Filling a row from left to right fills the top boundary and then moves the top boundary down.

expand

Change direction to down

Update direction from right (0) to down (1) to fill the right column next.

💡 Changing direction after filling a boundary ensures spiral movement.

Line:

direction = (direction + 1) % 4

💡 Direction cycles through 0:right, 1:down, 2:left, 3:up to control spiral movement.

fill_cells

Fill right column moving down

Fill the rightmost column from top to bottom with numbers 4 and 5. Increment num after each fill.

💡 Filling down the right column completes the right boundary of the current spiral layer.

Line:

for row in range(top, bottom + 1):
    matrix[row][right] = num
    num += 1
right -= 1

💡 Filling a column downward fills the right boundary and then moves the right boundary left.

expand

Change direction to left

Update direction from down (1) to left (2) to fill the bottom row next.

💡 Changing direction after filling a boundary ensures spiral movement.

Line:

direction = (direction + 1) % 4

💡 Direction cycles through 0:right, 1:down, 2:left, 3:up to control spiral movement.

fill_row

Fill bottom row moving left

Fill the bottom row from right to left with numbers 6, 7. Increment num after each fill.

💡 Filling the bottom row completes the bottom boundary of the current spiral layer.

Line:

for col in range(right, left - 1, -1):
    matrix[bottom][col] = num
    num += 1
bottom -= 1

💡 Filling a row from right to left fills the bottom boundary and then moves the bottom boundary up.

expand

Change direction to up

Update direction from left (2) to up (3) to fill the left column next.

💡 Changing direction after filling a boundary ensures spiral movement.

Line:

direction = (direction + 1) % 4

💡 Direction cycles through 0:right, 1:down, 2:left, 3:up to control spiral movement.

fill_cells

Fill left column moving up

Fill the leftmost column from bottom to top with number 8. Increment num after fill.

💡 Filling up the left column completes the left boundary of the current spiral layer.

Line:

for row in range(bottom, top - 1, -1):
    matrix[row][left] = num
    num += 1
left += 1

💡 Filling a column upward fills the left boundary and then moves the left boundary right.

expand

Change direction to right

Update direction from up (3) to right (0) to fill the inner top row next.

💡 Changing direction after filling a boundary ensures spiral movement.

Line:

direction = (direction + 1) % 4

💡 Direction cycles through 0:right, 1:down, 2:left, 3:up to control spiral movement.

fill_row

Fill inner top row moving right

Fill the remaining cell in the inner top row with number 9. Increment num after fill.

💡 Filling the last cell completes the spiral fill.

Line:

for col in range(left, right + 1):
    matrix[top][col] = num
    num += 1
top += 1

💡 Filling the last cell completes the spiral and moves the top boundary down.

prune

Check boundaries to end loop

Check if left <= right and top <= bottom to continue. Since top (2) > bottom (1), loop ends.

💡 Boundary checks determine when the spiral filling is complete.

Line:

while left <= right and top <= bottom:

💡 When boundaries cross, all cells are filled and the algorithm stops.

reconstruct

Return final matrix

Return the fully filled matrix as the final result.

💡 Returning the matrix completes the algorithm.

Line:

return matrix

💡 The matrix now contains numbers 1 to 9 in spiral order.

def generateMatrix(n):
    matrix = [[0]*n for _ in range(n)]  # STEP 1
    top, bottom = 0, n - 1  # STEP 1
    left, right = 0, n - 1  # STEP 1
    num = 1  # STEP 1
    direction = 0  # 0:right, 1:down, 2:left, 3:up  # STEP 1
    while left <= right and top <= bottom:  # STEP 11
        if direction == 0:  # STEP 2,10
            for col in range(left, right + 1):  # STEP 2,10
                matrix[top][col] = num  # STEP 2,10
                num += 1  # STEP 2,10
            top += 1  # STEP 2,10
        elif direction == 1:  # STEP 4
            for row in range(top, bottom + 1):  # STEP 4
                matrix[row][right] = num  # STEP 4
                num += 1  # STEP 4
            right -= 1  # STEP 4
        elif direction == 2:  # STEP 6
            for col in range(right, left - 1, -1):  # STEP 6
                matrix[bottom][col] = num  # STEP 6
                num += 1  # STEP 6
            bottom -= 1  # STEP 6
        else:  # STEP 8
            for row in range(bottom, top - 1, -1):  # STEP 8
                matrix[row][left] = num  # STEP 8
                num += 1  # STEP 8
            left += 1  # STEP 8
        direction = (direction + 1) % 4  # STEP 3,5,7,9
    return matrix  # STEP 12

📊

Spiral Matrix II (Fill Outward Spiral) - Watch the Algorithm Execute, Step by Step

Watching each step shows exactly how boundaries and directions control the spiral fill, making the logic clear without guessing.

setup

direction

0

1

right

2

Result: 0

fill_row

direction

0

top

1

right

2

Result: 3

expand

left

0

direction

1

right

2

Result: 3

fill_cells

left

0

direction

1

bottom

2

Result: 5

expand

left

0

right

1

direction

2

Result: 5

fill_row

left

0

right

1

direction

2

Result: 7

expand

left

0

right

1

2

Result: 7

fill_cells

0

right

1

2

Result: 8

expand

direction

0

right

1

2

Result: 8

fill_row

direction

0

right

1

top

2

Result: 9

prune

direction

0

right

1

top

2

Result: 9

record

0

1

2

Result: 9

Key Takeaways

✓ The spiral is controlled by shrinking boundaries and cycling directions.

This insight is hard to see from code alone because the boundary updates and direction changes are subtle but critical.

✓ Each direction fills a row or column fully before changing direction.

Visualizing this shows why the algorithm never overwrites cells and fills the matrix layer by layer.

✓ The loop ends when boundaries cross, indicating the matrix is fully filled.

Understanding this stopping condition clarifies why the algorithm terminates exactly after filling all cells.

Practice

1. Consider the following code snippet implementing the in-place Game of Life update. Given the input board = [[0,1,0],[0,1,1],[1,1,0]], what is the value of board[1][1] after the first nested loop completes (before the final decoding loop)?

easy

A. 1

B. 2

C. 3

D. 0

Solution

1. Step 1: Count live neighbors of cell (1,1)

   Neighbors: (0,0)=0, (0,1)=1, (0,2)=0, (1,0)=0, (1,2)=1, (2,0)=1, (2,1)=1, (2,2)=0. Live neighbors in (1, 2) states are 4 (cells with 1 or 2 are live).

2. Step 2: Apply rules for live cell with 4 neighbors

   Since live_neighbors=4 > 3, cell (1,1) changes from live (1) to 2 (live->dead) in encoding.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   4 neighbors -> live cell dies -> encoded as 2 [OK]

Hint: Count neighbors including encoded live states (1,2) [OK]

Common Mistakes:

• Counting only original 1 states, ignoring encoded 2
• Miscounting neighbors due to boundary errors
• Confusing final state with encoded intermediate state

2. The following code attempts to compute the sum of the diagonals of a square matrix. Identify the line that contains a subtle bug causing incorrect results for odd-sized matrices.

def diagonalSum(mat):
    total = 0
    n = len(mat)
    for i in range(n):
        total += mat[i][i] + mat[i][n - 1 - i]
    if n % 2 == 1:
        total += mat[n//2][n//2]  # Bug here
    return total

medium

A. Line 5: total += mat[i][i] + mat[i][n - 1 - i]

B. Line 8: total += mat[n//2][n//2] # Bug here

C. Line 7: if n % 2 == 1:

D. Line 4: for i in range(n):

Solution

1. Step 1: Understand double counting of center element

   For odd n, the center element mat[n//2][n//2] is added twice in the loop.

2. Step 2: Identify the fix

   The code should subtract the center element once to avoid double counting, but line 8 adds it again, increasing total incorrectly.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Adding center element again causes sum to be too large [OK]

Hint: Center element must be subtracted once if n is odd [OK]

Common Mistakes:

• Adding instead of subtracting center element
• Incorrect index calculation for secondary diagonal
• Ignoring odd-sized matrix special case

3. 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

4. Suppose the Game of Life rules are modified so that cells can be in one of three states: dead, alive, or dormant, and the next state depends on neighbors' states with more complex transitions. Which modification to the in-place encoding approach is necessary to correctly update the board?

hard

A. Use a larger integer encoding scheme with more states to represent current and next states simultaneously.

B. Switch to copying the entire board each iteration to avoid encoding complexity.

C. Update cells immediately without encoding since more states simplify neighbor counting.

D. Ignore dormant state neighbors during counting to reduce complexity.

Solution

1. Step 1: Understand the need for more states

   With three possible states and complex transitions, encoding must represent both current and next states simultaneously.

2. Step 2: Choose encoding approach

   Using a larger integer encoding scheme (e.g., 6 or more states) allows in-place updates without losing original state info.

3. Step 3: Reject naive approaches

   Copying the board increases space; immediate updates corrupt neighbor info; ignoring dormant neighbors breaks rules.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   More states require richer encoding to preserve info [OK]

Hint: More states require more encoding bits, not naive copying [OK]

Common Mistakes:

• Switching to copying board wastes space
• Immediate updates corrupt neighbor counts
• Ignoring certain neighbors breaks rules

5. Suppose the problem is modified so that instead of zeroing rows and columns, you must zero only the rows and columns of the first zero found (in row-major order). Which modification to the optimal in-place algorithm correctly implements this variant?

hard

A. Use sets to track all zero positions but only apply zeroing to the first zero's row and column after scanning.

B. Use the original algorithm but stop marking after the first zero is found, then zero rows and columns accordingly.

C. Scan the matrix once to find the first zero, then zero its entire row and column directly without using flags.

D. Modify the flagging approach to mark only the first zero's row and column, ignoring others.

Solution

1. Step 1: Understand the variant

   Only the first zero's row and column should be zeroed, so no need to track multiple zeros.

2. Step 2: Choose direct zeroing

   Scanning once to find the first zero, then zeroing its row and column directly is simplest and correct.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Direct zeroing after first zero found matches problem variant [OK]

Hint: Stop at first zero, zero its row and column directly [OK]

Common Mistakes:

• Continuing to mark all zeros wastes time and zeroes extra rows/columns
• Trying to adapt flagging for only one zero complicates logic unnecessarily
• Using sets but applying zeroing to all zeros instead of just first