Spiral Matrix Traversal in DSA C++ - Execution Trace

Concept Flow - Spiral Matrix Traversal

Start with boundaries: top, bottom, left, right

↓

Traverse from left to right along top row

↓

Move top boundary down

↓

Traverse from top to bottom along right column

↓

Move right boundary left

↓

Traverse from right to left along bottom row

↓

Move bottom boundary up

↓

Traverse from bottom to top along left column

↓

Move left boundary right

↓

Check if boundaries crossed

Yes↓

End traversal

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

Execution Sample

DSA C++

int top = 0, bottom = rows - 1;
int left = 0, right = cols - 1;
while (top <= bottom && left <= right) {
  // Traverse top row left->right
  // Traverse right column top->bottom
  // Traverse bottom row right->left
  // Traverse left column bottom->top
  // Adjust boundaries
}

This code moves around the matrix edges in a spiral, adjusting boundaries after each side traversal.

Execution Table

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

💡 Traversal ends because top boundary (2) crossed bottom boundary (1).

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 8	After Step 10	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
spiral_order	[]	[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 check 'top <= bottom' and 'left <= right' before each traversal?

Because after moving boundaries inward, they may cross, meaning all elements are visited. This stops extra traversals as shown in step 11 of execution_table.

Why do we move boundaries after traversing each side?

Moving boundaries shrinks the matrix edges inward, preventing revisiting elements. For example, after traversing the top row, top moves down (step 2) to avoid re-traversal.

Why does the spiral_order list grow after each side traversal?

Because each traversal adds elements from one side of the current boundary, gradually collecting all matrix elements in spiral order as shown in the 'Elements Added' column.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'top' after step 6?

A 1

B 2

C 0

D 3

💡 Hint

Check variable_tracker row for 'top' after step 6.

At which step does the traversal add the element '5' to spiral_order?

A Step 7

B Step 9

C Step 10

D Step 11

💡 Hint

Look at 'Elements Added' column in execution_table for step 9.

If the matrix had 4 rows and 4 columns, how would the boundaries change after the first full spiral cycle?

A top=1, bottom=2, left=0, right=3

B top=1, bottom=3, left=1, right=3

C top=1, bottom=2, left=1, right=2

D top=0, bottom=3, left=1, right=2

💡 Hint

After traversing all four sides once, each boundary moves inward by one.

Concept Snapshot

Spiral Matrix Traversal:
- Use four boundaries: top, bottom, left, right
- Traverse edges in order: top row, right column, bottom row, left column
- After each side, move the boundary inward
- Continue while top <= bottom and left <= right
- Collect elements in spiral order without repeats

Full Transcript

Spiral Matrix Traversal moves around the edges of a matrix in a spiral pattern. We start with four boundaries: top, bottom, left, and right. We first traverse the top row from left to right, then move the top boundary down. 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. After that, we traverse the left column from bottom to top, and move the left boundary right. We repeat these steps until the top boundary crosses the bottom or the left crosses the right, meaning all elements have been visited. This process collects all elements in spiral order without repeats.

Practice

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

easy

A. Traverse only the diagonal elements of the matrix

B. Traverse the matrix row by row from top to bottom

C. Traverse the matrix column by column from left to right

D. Traverse the matrix in a circular pattern starting from the outer layer moving inward

Solution

1. Step 1: Understand traversal pattern

   Spiral traversal means moving around the edges of the matrix and then moving inward layer by layer.

2. Step 2: Compare options

   Only Traverse the matrix in a circular pattern starting from the outer layer moving inward describes moving in a circular pattern from outer to inner layers, which matches spiral traversal.

3. Final Answer:

   Traverse the matrix in a circular pattern starting from the outer layer moving inward -> Option D

4. Quick Check:

   Spiral traversal = circular outer to inner [OK]

Hint: Spiral means circle around edges then go inside [OK]

Common Mistakes:

• Confusing spiral with row-wise or column-wise traversal
• Thinking spiral means diagonal traversal
• Ignoring the inward movement after outer layer

2. Which of the following C++ code snippets correctly initializes the boundaries for spiral traversal of an m x n matrix?

easy

A. int top = 0, bottom = n - 1, left = 0, right = m - 1;

B. int top = 0, bottom = m - 1, left = 0, right = n - 1;

C. int top = 1, bottom = m, left = 1, right = n;

D. int top = m - 1, bottom = 0, left = n - 1, right = 0;

Solution

1. Step 1: Understand boundary variables

   Top and bottom represent row boundaries, left and right represent column boundaries. For an m x n matrix, top starts at 0, bottom at m-1, left at 0, right at n-1.

2. Step 2: Check each option

   int top = 0, bottom = m - 1, left = 0, right = n - 1; correctly sets top=0, bottom=m-1, left=0, right=n-1. Others have reversed or incorrect assignments.

3. Final Answer:

   int top = 0, bottom = m - 1, left = 0, right = n - 1; -> Option B

4. Quick Check:

   Boundaries = top=0, bottom=m-1, left=0, right=n-1 [OK]

Hint: Top/left start at 0; bottom/right at size minus one [OK]

Common Mistakes:

• Swapping m and n in boundary initialization
• Starting boundaries at 1 instead of 0
• Confusing row and column boundaries

3. What is the output of the following C++ code snippet for spiral traversal?

int matrix[3][3] = {
  {1, 2, 3},
  {4, 5, 6},
  {7, 8, 9}
};

int top = 0, bottom = 2, left = 0, right = 2;

while (top <= bottom && left <= right) {
  for (int i = left; i <= right; i++)
    std::cout << matrix[top][i] << " ";
  top++;
  for (int i = top; i <= bottom; i++)
    std::cout << matrix[i][right] << " ";
  right--;
  if (top <= bottom) {
    for (int i = right; i >= left; i--)
      std::cout << matrix[bottom][i] << " ";
    bottom--;
  }
  if (left <= right) {
    for (int i = bottom; i >= top; i--)
      std::cout << matrix[i][left] << " ";
    left++;
  }
}

medium

A. 1 2 3 4 5 6 7 8 9

B. 1 4 7 8 9 6 3 2 5

C. 1 2 3 6 9 8 7 4 5

D. 9 8 7 6 5 4 3 2 1

Solution

1. Step 1: Trace the spiral traversal

   First top row: 1 2 3
   Right column down: 6 9
   Bottom row left: 8 7
   Left column up: 4
   Next inner layer top row: 5

2. Step 2: Combine all elements in order

   Combined output: 1 2 3 6 9 8 7 4 5

3. Final Answer:

   1 2 3 6 9 8 7 4 5 -> Option C

4. Quick Check:

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

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

Common Mistakes:

• Printing rows or columns in wrong order
• Skipping inner elements like 5
• Repeating elements or missing boundaries update

4. Identify the bug in this spiral traversal code snippet:

int top = 0, bottom = m - 1, left = 0, right = n - 1;
while (top < bottom && left < right) {
  for (int i = left; i <= right; i++) cout << matrix[top][i] << " ";
  top++;
  for (int i = top; i <= bottom; i++) cout << matrix[i][right] << " ";
  right--;
  for (int i = right; i >= left; i--) cout << matrix[bottom][i] << " ";
  bottom--;
  for (int i = bottom; i >= top; i--) cout << matrix[i][left] << " ";
  left++;
}

medium

A. The while loop condition should use <= instead of < to include all layers

B. The for loops should use < instead of <= to avoid out-of-bound errors

C. The variables top, bottom, left, right are not initialized correctly

D. The code misses printing the diagonal elements

Solution

1. Step 1: Analyze loop condition

   The while loop uses 'top < bottom && left < right', which skips the last layer when top == bottom or left == right.

2. Step 2: Correct condition for full traversal

   Changing to 'top <= bottom && left <= right' ensures the last single row or column is included in traversal.

3. Final Answer:

   The while loop condition should use <= instead of < to include all layers -> Option A

4. Quick Check:

   Use <= in loop condition to cover all layers [OK]

Hint: Use <= in while condition to cover last layer [OK]

Common Mistakes:

• Using < causes missing last row or column
• Changing for loops to < causes skipping elements
• Not updating boundaries after each traversal

5. Given a non-square matrix:

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

Which is the correct spiral traversal output?

hard

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

B. 1 2 3 4 8 12 11 10 9 5 6 7 0

C. 1 5 9 10 11 12 8 4 3 2 6 7

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

Solution

1. Step 1: Trace spiral on 3x4 matrix

   Top row: 1 2 3 4
   Right column down: 8 12
   Bottom row left: 11 10 9
   Left column up: 5
   Inner top row: 6 7

2. Step 2: Combine elements in order

   Combined output: 1 2 3 4 8 12 11 10 9 5 6 7

3. Final Answer:

   1 2 3 4 8 12 11 10 9 5 6 7 -> Option A

4. Quick Check:

   Spiral order for 3x4 matrix = 1 2 3 4 8 12 11 10 9 5 6 7 [OK]

Hint: Follow edges carefully, handle rectangular shape [OK]

Common Mistakes:

• Adding extra elements like 0
• Mixing inner elements order
• Swapping 6 and 7 positions