Spiral Matrix (Read Outward Spiral)

▶

Steps

setup

Initialize boundaries and result

Set top and left to 0, bottom and right to last indices of rows and columns respectively. Initialize an empty result list to store spiral order.

💡 Boundaries define the current layer of the matrix to traverse. Starting with full matrix boundaries is essential.

Line:

top, bottom = 0, len(matrix) - 1
left, right = 0, len(matrix[0]) - 1
result = []

💡 Boundaries frame the current traversal layer and will shrink inward after each side is processed.

traverse

Traverse top row left to right

Collect elements from the top row, from left to right boundary indices, and append them to the result.

💡 This step collects the first row of the current layer, starting the spiral traversal.

Line:

result.extend(matrix[top][left:right+1])
top += 1

💡 Traversing the top row fully before moving boundaries ensures correct spiral order.

traverse

Traverse right column top to bottom

Iterate down the right column from the new top boundary to bottom boundary, appending each element to result.

💡 This step collects the rightmost column of the current layer, continuing the spiral clockwise.

Line:

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

💡 Traversing the right column after the top row completes the first two sides of the spiral layer.

compare

Check if bottom row remains to traverse

Check if top boundary is still less than or equal to bottom boundary to decide if bottom row traversal is needed.

💡 This condition prevents re-traversing rows when boundaries cross.

Line:

if top <= bottom:

💡 Boundary checks ensure traversal only happens within valid matrix layers.

traverse

Traverse bottom row right to left

Traverse the bottom row from right boundary to left boundary, appending elements in reverse order to result.

💡 This step collects the bottom row of the current layer in reverse to maintain spiral order.

Line:

for col in range(right, left - 1, -1):
    result.append(matrix[bottom][col])
bottom -= 1

💡 Reversing the column iteration is necessary to traverse the bottom row from right to left.

compare

Check if left column remains to traverse

Check if left boundary is still less than or equal to right boundary to decide if left column traversal is needed.

💡 This condition prevents re-traversing columns when boundaries cross.

Line:

if left <= right:

💡 Boundary checks ensure traversal only happens within valid matrix layers.

traverse

Traverse left column bottom to top

Traverse the left column from bottom boundary to top boundary, appending elements in reverse order to result.

💡 This step collects the left column of the current layer in reverse to maintain spiral order.

Line:

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

💡 Reversing the row iteration is necessary to traverse the left column from bottom to top.

compare

Check loop continuation condition

Check if left boundary is still less than or equal to right boundary and top boundary is less than or equal to bottom boundary to continue traversal.

💡 This condition controls the main loop to stop when all layers are traversed.

Line:

while left <= right and top <= bottom:

💡 Loop continues as there is still a valid submatrix to traverse.

traverse

Traverse remaining top row (center element)

Traverse the top row from left to right boundary (which are equal), collecting the center element 5.

💡 This step collects the last remaining element in the center of the matrix.

Line:

result.extend(matrix[top][left:right+1])
top += 1

💡 When boundaries converge, only one element remains to be collected.

compare

Check loop termination condition

Check if left boundary is still less than or equal to right boundary and top boundary is less than or equal to bottom boundary to continue traversal.

💡 This condition controls the main loop to stop when all layers are traversed.

Line:

while left <= right and top <= bottom:

💡 Boundaries have crossed, indicating traversal is complete.

from typing import List

def spiralOrder(matrix: List[List[int]]) -> List[int]:
    if not matrix or not matrix[0]:
        return []
    result = []  # STEP 1
    top, bottom = 0, len(matrix) - 1  # STEP 1
    left, right = 0, len(matrix[0]) - 1  # STEP 1
    while left <= right and top <= bottom:  # STEP 8,10
        result.extend(matrix[top][left:right+1])  # STEP 2,9
        top += 1  # STEP 2,9
        for row in range(top, bottom + 1):  # STEP 3
            result.append(matrix[row][right])
        right -= 1  # STEP 3
        if top <= bottom:  # STEP 4
            for col in range(right, left - 1, -1):  # STEP 5
                result.append(matrix[bottom][col])
            bottom -= 1  # STEP 5
        if left <= right:  # STEP 6
            for row in range(bottom, top - 1, -1):  # STEP 7
                result.append(matrix[row][left])
            left += 1  # STEP 7
    return result

📊

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

Watching the algorithm move boundaries and collect elements stepwise reveals the spiral traversal pattern clearly, which is hard to grasp from code alone.

setup

left

1

0

2

1

right

3

2

4

3

5

4

6

5

7

6

8

7

9

8

Result: []

record

left

1

0

top

2

1

right

3

2

4

3

5

4

6

5

7

6

8

7

9

8

Result: [1,2,3]

record

left

1

0

right

2

1

bottom

3

2

4

3

5

4

6

5

7

6

8

7

9

8

Result: [1,2,3,6,9]

compare

left

1

0

right

2

1

bottom

3

2

4

3

5

4

6

5

7

6

8

7

9

8

Result: [1,2,3,6,9]

record

left

1

0

right

2

1

3

2

4

3

5

4

6

5

7

6

8

7

9

8

Result: [1,2,3,6,9,8,7]

compare

left

1

0

right

2

1

3

2

4

3

5

4

6

5

7

6

8

7

9

8

Result: [1,2,3,6,9,8,7]

record

1

0

right

2

1

3

2

4

3

5

4

6

5

7

6

8

7

9

8

Result: [1,2,3,6,9,8,7,4]

compare

1

0

right

2

1

3

2

4

3

5

4

6

5

7

6

8

7

9

8

Result: [1,2,3,6,9,8,7,4]

record

1

0

right

2

1

top

3

2

4

3

5

4

6

5

7

6

8

7

9

8

Result: [1,2,3,6,9,8,7,4,5]

compare

1

0

right

2

1

top

3

2

4

3

5

4

6

5

7

6

8

7

9

8

Result: [1,2,3,6,9,8,7,4,5]

Key Takeaways

✓ The spiral traversal is controlled by shrinking boundaries that define the current layer to traverse.

This insight is hard to see from code alone because the boundary variables move subtly and control the loop.

✓ Each side of the matrix layer is traversed in a specific order: top row left-to-right, right column top-to-bottom, bottom row right-to-left, left column bottom-to-top.

Visualizing this order helps understand why the algorithm uses different loops and directions for each side.

✓ Boundary checks before traversing bottom row and left column prevent duplicate traversals when boundaries cross.

Seeing these checks in action clarifies why the algorithm avoids errors and stops correctly.

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. What is the time complexity of the optimal staircase search algorithm for counting negative numbers in an m x n sorted matrix, and why?

medium

A. O(m * n) because each element might be visited once.

B. O(n) because it only scans the top row and last column.

C. O(m log n) because it performs binary search on each row.

D. O(m + n) because the algorithm moves at most m times down and n times left.

Solution

1. Step 1: Analyze movement in matrix

   The algorithm starts at top-right and moves left or down, never revisiting cells.

2. Step 2: Count maximum moves

   Maximum moves down = m, maximum moves left = n, total moves ≤ m + n.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Linear traversal along edges, not full matrix scan [OK]

Hint: Moves only left or down once per step, total ≤ m+n [OK]

Common Mistakes:

• Confusing with brute force O(m*n)
• Assuming binary search per row
• Ignoring that each cell is visited once

3. Consider this buggy code snippet for diagonal traversal. Which line contains the subtle bug that causes incorrect traversal or index errors?

def findDiagonalOrder(mat):
    if not mat or not mat[0]:
        return []
    m, n = len(mat), len(mat[0])
    result = []
    for d in range(m + n - 1):
        r_start = max(0, d - n + 1)
        r_end = min(d, m - 1)
        if d % 2 == 0:
            for r in range(r_start, r_end + 1):  # Bug here: direction wrong
                c = d - r
                result.append(mat[r][c])
        else:
            for r in range(r_end, r_start - 1, -1):
                c = d - r
                result.append(mat[r][c])
    return result

medium

A. Line with 'r_start = max(0, d - n + 1)'

B. Line with 'for r in range(r_start, r_end + 1):' inside even diagonal block

C. Line with 'c = d - r' inside loops

D. Line with 'for d in range(m + n - 1):'

Solution

1. Step 1: Identify traversal direction for even diagonals

   Even diagonals must traverse from r_end down to r_start (descending).

2. Step 2: Check loop direction in buggy code

   The loop uses ascending range from r_start to r_end, which is incorrect and causes wrong order or index errors.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Fixing loop direction restores correct traversal [OK]

Hint: Even diagonals traverse downward (descending indices) [OK]

Common Mistakes:

• Using ascending loop for even diagonals causing order errors

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

5. What is the space complexity of the optimal in-place layer-by-layer rotation algorithm for an n x n matrix, and why might some candidates mistakenly think it is higher?

medium

A. O(n^2) because the entire matrix is modified in place.

B. O(log n) because the algorithm processes layers recursively.

C. O(n) due to the recursion stack or auxiliary arrays used during rotation.

D. O(1) because only a fixed number of variables are used regardless of matrix size.

Solution

1. Step 1: Identify space usage

   The algorithm uses only a few variables (indices, temp storage) regardless of matrix size.

2. Step 2: Understand common misconceptions

   Some think space is O(n) or more due to confusion with extra matrix or recursion, but no extra arrays or recursion are used.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Only constant extra variables used, so space is O(1) [OK]

Hint: In-place means constant extra space regardless of input size [OK]

Common Mistakes:

• Confusing time complexity with space
• Assuming recursion or extra arrays are used