Spiral Matrix Traversal in DSA Python - Execution Trace

Concept Flow - Spiral Matrix Traversal

Start with boundaries: top, bottom, left, right

↓

Traverse from left to right on top row

↓

Move top boundary down

↓

Traverse from top to bottom on right column

↓

Move right boundary left

↓

Traverse from right to left on bottom row

↓

Move bottom boundary up

↓

Traverse from bottom to top on left column

↓

Move left boundary right

↓

Check if boundaries crossed

Yes↓

End

We move around the matrix edges in a spiral by updating boundaries after each side traversal until all elements are visited.

Execution Sample

DSA Python

def spiral_traversal(matrix):
    result = []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    while left <= right and top <= bottom:
        for i in range(left, right + 1):
            result.append(matrix[top][i])
        top += 1
        for i in range(top, bottom + 1):
            result.append(matrix[i][right])
        right -= 1
        if top <= bottom:
            for i in range(right, left - 1, -1):
                result.append(matrix[bottom][i])
            bottom -= 1
        if left <= right:
            for i in range(bottom, top - 1, -1):
                result.append(matrix[i][left])
            left += 1
    return result

This code starts traversing the top row from left to right and collects elements in spiral order.

Execution Table

Step	Operation	Boundaries (top,bottom,left,right)	Elements Added	Visual State of Matrix Traversed
1	Initialize boundaries	(0,2,0,2)	[]	[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
2	Traverse top row left->right	(0,2,0,2)	[1,2,3]	[1] [2] [3] [ ] [ ] [ ] [ ] [ ] [ ]
3	Move top boundary down	(1,2,0,2)	[1,2,3]	[1] [2] [3] [ ] [ ] [ ] [ ] [ ] [ ]
4	Traverse right column top->bottom	(1,2,0,2)	[1,2,3,6,9]	[1] [2] [3] [ ] [ ] [6] [ ] [ ] [9]
5	Move right boundary left	(1,2,0,1)	[1,2,3,6,9]	[1] [2] [3] [ ] [ ] [6] [ ] [ ] [9]
6	Traverse bottom row right->left	(1,2,0,1)	[1,2,3,6,9,8,7]	[1] [2] [3] [ ] [ ] [6] [7] [8] [9]
7	Move bottom boundary up	(1,1,0,1)	[1,2,3,6,9,8,7]	[1] [2] [3] [ ] [ ] [6] [7] [8] [9]
8	Traverse left column bottom->top	(1,1,0,1)	[1,2,3,6,9,8,7,4]	[1] [2] [3] [4] [ ] [6] [7] [8] [9]
9	Move left boundary right	(1,1,1,1)	[1,2,3,6,9,8,7,4]	[1] [2] [3] [4] [ ] [6] [7] [8] [9]
10	Traverse top row left->right	(1,1,1,1)	[1,2,3,6,9,8,7,4,5]	[1] [2] [3] [4] [5] [6] [7] [8] [9]
11	Move top boundary down	(2,1,1,1)	[1,2,3,6,9,8,7,4,5]	[1] [2] [3] [4] [5] [6] [7] [8] [9]
12	Check boundaries crossed	(2,1,1,1)	[1,2,3,6,9,8,7,4,5]	Traversal complete

💡 Top boundary (2) > bottom boundary (1), so traversal ends

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	After Step 9	After Step 11	Final
top	0	1	1	1	1	2	2
bottom	2	2	2	1	1	1	1
left	0	0	0	0	1	1	1
right	2	2	1	1	1	1	1
result	[]	[1,2,3]	[1,2,3,6,9]	[1,2,3,6,9,8,7]	[1,2,3,6,9,8,7,4]	[1,2,3,6,9,8,7,4,5]	[1,2,3,6,9,8,7,4,5]

Key Moments - 3 Insights

Why do we update the boundaries after each side traversal?

Updating boundaries (top, bottom, left, right) after traversing a side prevents revisiting the same row or column. For example, after traversing the top row (step 3), top moves down to avoid repeating that row (see execution_table rows 2 and 3).

Why does the loop stop when top > bottom or left > right?

The loop condition ensures we only traverse valid rows and columns. When top boundary crosses bottom or left crosses right (step 12), it means all elements are visited, so traversal ends (see exit_note).

How do we know which direction to traverse next?

We follow a fixed order: left to right (top row), top to bottom (right column), right to left (bottom row), bottom to top (left column). This repeats while boundaries allow (see concept_flow).

Visual Quiz - 3 Questions

Look at the execution_table at step 6, which elements were added to the result?

A [1,2,3,6,9]

B [7,8,9]

C [1,2,3,6,9,8,7]

D [1,2,3]

💡 Hint

Check the 'Elements Added' column at step 6 in execution_table

At which step does the left boundary move from 0 to 1?

A Step 9

B Step 7

C Step 5

D Step 3

💡 Hint

Look at the 'Boundaries' column in execution_table rows and variable_tracker for 'left' variable

If the matrix was 4x4, how would the exit condition change?

A Loop ends after fixed 4 iterations

B Loop ends when top > bottom or left > right, same as 3x3

C Loop ends when top == bottom and left == right

D Loop never ends

💡 Hint

Refer to exit_note and concept_flow about boundary crossing conditions

Concept Snapshot

Spiral Matrix Traversal:
- Use four boundaries: top, bottom, left, right
- Traverse edges in order: left->right, top->bottom, right->left, bottom->top
- After each edge, update the corresponding boundary
- Stop when boundaries cross (top > bottom or left > right)
- Collect elements in a list in spiral order

Full Transcript

Spiral Matrix Traversal moves around the matrix edges in a spiral pattern. We start with boundaries at the edges: top row, bottom row, left column, and right column. We first traverse the top row from left to right, then move the top boundary down to avoid revisiting. Next, we traverse the right column from top to bottom, then move the right boundary left. Then we traverse the bottom row from right to left, and move the bottom boundary up. Finally, we traverse the left column from bottom to top, and move the left boundary right. We repeat this process until the top boundary crosses the bottom or the left boundary crosses the right, meaning all elements are visited. This method ensures every element is visited exactly once in spiral order.

Practice

1. What is the main idea behind Spiral Matrix Traversal?

easy

A. Traverse the matrix in a spiral order starting from the top-left corner

B. Traverse the matrix row by row from left to right only

C. Traverse the matrix column by column from top to bottom only

D. Traverse the matrix diagonally from top-left to bottom-right

Solution

1. Step 1: Understand traversal pattern

   Spiral traversal means moving around the matrix edges and gradually moving inward in a circular pattern.

2. Step 2: Identify starting point and direction

   It starts at the top-left corner and moves right, then down, then left, then up, repeating until all elements are visited.

3. Final Answer:

   Traverse the matrix in a spiral order starting from the top-left corner -> Option A

4. Quick Check:

   Spiral traversal = circular edge-wise movement [OK]

Hint: Think of peeling an onion layer by layer in a circle [OK]

Common Mistakes:

• Confusing spiral with row-wise or column-wise traversal
• Starting traversal from the wrong corner
• Ignoring direction changes after each edge

2. Which of the following Python code snippets correctly initializes the boundaries for spiral traversal of a matrix named matrix?

easy

A. top = 1; bottom = len(matrix); left = 1; right = len(matrix[0])

B. top = 0; bottom = len(matrix) - 1; left = 0; right = len(matrix[0]) - 1

C. top = 0; bottom = len(matrix); left = 0; right = len(matrix[0])

D. top = 1; bottom = len(matrix) - 1; left = 1; right = len(matrix[0]) - 1

Solution

1. Step 1: Understand matrix boundaries

   For a matrix, top and left start at 0, bottom is last row index (length - 1), right is last column index (length - 1).

2. Step 2: Check each option

   top = 0; bottom = len(matrix) - 1; left = 0; right = len(matrix[0]) - 1 correctly sets top=0, bottom=len(matrix)-1, left=0, right=len(matrix[0])-1 which matches the matrix indices.

3. Final Answer:

   top = 0; bottom = len(matrix) - 1; left = 0; right = len(matrix[0]) - 1 -> Option B

4. Quick Check:

   Boundary indices start at 0 and end at length-1 [OK]

Hint: Remember Python indexing starts at 0, so subtract 1 for last index [OK]

Common Mistakes:

• Using length instead of length - 1 for bottom and right
• Starting top or left at 1 instead of 0
• Mixing row and column lengths

3. What is the output of the following Python code?

matrix = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
]
result = []
top, bottom = 0, 2
left, right = 0, 2
while top <= bottom and left <= right:
    for i in range(left, right + 1):
        result.append(matrix[top][i])
    top += 1
    for i in range(top, bottom + 1):
        result.append(matrix[i][right])
    right -= 1
    for i in range(right, left - 1, -1):
        result.append(matrix[bottom][i])
    bottom -= 1
    for i in range(bottom, top - 1, -1):
        result.append(matrix[i][left])
    left += 1
print(result)

medium

A. [1, 2, 3, 6, 9, 8, 7, 4, 5]

B. [1, 2, 3, 6, 9, 8, 7, 5, 4]

C. [1, 2, 3, 6, 9, 7, 8, 4, 5]

D. [1, 2, 3, 6, 9, 8, 7, 4]

Solution

1. Step 1: Traverse top row left to right

   Elements: 1, 2, 3 added to result.

2. Step 2: Traverse right column top to bottom

   Elements: 6, 9 added to result.

3. Step 3: Traverse bottom row right to left

   Elements: 8, 7 added to result.

4. Step 4: Traverse left column bottom to top

   Element: 4 added to result.

5. Step 5: Inner layer traversal

   Only element 5 remains, added last.

6. Final Answer:

   [1, 2, 3, 6, 9, 8, 7, 4, 5] -> Option A

7. Quick Check:

   Spiral order = [1,2,3,6,9,8,7,4,5] [OK]

Hint: Follow edges clockwise, then move inward layer by layer [OK]

Common Mistakes:

• Skipping the last inner element
• Repeating elements or missing elements
• Wrong direction in bottom or left traversal

4. The following code attempts spiral traversal but produces an error. What is the main bug?

matrix = [[1,2,3],[4,5,6],[7,8,9]]
top, bottom = 0, 2
left, right = 0, 2
result = []
while top <= bottom and left <= right:
    for i in range(left, right + 1):
        result.append(matrix[top][i])
    top += 1
    for i in range(top, bottom + 1):
        result.append(matrix[i][right])
    right -= 1
    for i in range(right, left - 1, -1):
        result.append(matrix[bottom][i])
    bottom -= 1
    for i in range(bottom, top - 1, -1):
        result.append(matrix[i][left])
    left += 1
print(result)

medium

A. The code uses incorrect range in the first for loop

B. The code uses wrong indices for left and right boundaries

C. The code does not check if top <= bottom before traversing bottom row

D. The code misses incrementing the left boundary

Solution

1. Step 1: Analyze loop conditions

   The while loop checks top <= bottom and left <= right before each full cycle.

2. Step 2: Identify missing checks inside loop

   After updating top and right, the code traverses bottom row and left column without checking if top <= bottom or left <= right again, causing index errors when boundaries cross.

3. Final Answer:

   The code does not check if top <= bottom before traversing bottom row -> Option C

4. Quick Check:

   Boundary checks needed before each edge traversal [OK]

Hint: Check boundaries before each edge traversal inside the loop [OK]

Common Mistakes:

• Assuming one boundary check per loop is enough
• Not updating boundaries correctly
• Ignoring empty or single-row/column matrices

5. Given a rectangular matrix of size 3x4:

matrix = [
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9, 10, 11, 12]
]

What is the spiral traversal output?

hard

A. [1, 2, 3, 4, 8, 12, 11, 10, 9, 6, 5, 7]

B. [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 7, 6]

C. ]6 ,7 ,5 ,9 ,01 ,11 ,21 ,8 ,4 ,3 ,2 ,1[

D. [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]

Solution

1. Step 1: Traverse top row left to right

   Elements: 1, 2, 3, 4 added.

2. Step 2: Traverse right column top to bottom

   Elements: 8, 12 added.

3. Step 3: Traverse bottom row right to left

   Elements: 11, 10, 9 added.

4. Step 4: Traverse left column bottom to top

   Element: 5 added.

5. Step 5: Traverse inner row left to right

   Elements: 6, 7 added.

6. Final Answer:

   [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7] -> Option D

7. Quick Check:

   Spiral order covers all elements layer by layer [OK]

Hint: Follow edges clockwise, then move inward carefully for rectangular matrices [OK]

Common Mistakes:

• Mixing order of inner elements
• Skipping or repeating elements in inner layers
• Confusing left column traversal direction