Spiral Matrix Traversal in DSA C - Execution Trace

Concept Flow - Spiral Matrix Traversal

Initialize 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

↓

Repeat or End

We keep four boundaries and move inward in a spiral: top row left to right, right column top to bottom, bottom row right to left, left column bottom to top, then shrink boundaries and repeat 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 and print edges
  // Update boundaries
}

This code traverses the matrix edges in spiral order by updating boundaries after each edge traversal.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Initialize boundaries	N/A	top=0, bottom=2, left=0, right=2	[[1,2,3],[4,5,6],[7,8,9]]
2	Traverse top row left to right	Elements visited: 1,2,3	top=0 -> top=1	[[1,2,3],[4,5,6],[7,8,9]] Visited: 1->2->3
3	Traverse right column top to bottom	Elements visited: 6,9	right=2 -> right=1	[[1,2,3],[4,5,6],[7,8,9]] Visited: 1->2->3->6->9
4	Traverse bottom row right to left	Elements visited: 8,7	bottom=2 -> bottom=1	[[1,2,3],[4,5,6],[7,8,9]] Visited: 1->2->3->6->9->8->7
5	Traverse left column bottom to top	Elements visited: 4	left=0 -> left=1	[[1,2,3],[4,5,6],[7,8,9]] Visited: 1->2->3->6->9->8->7->4
6	Traverse top row left to right (inner layer)	Elements visited: 5	top=1 -> top=2	[[1,2,3],[4,5,6],[7,8,9]] Visited: 1->2->3->6->9->8->7->4->5
7	Check boundaries	All elements visited	top=2, bottom=1, left=1, right=1 (top > bottom)	Traversal ends

💡 top boundary crossed bottom boundary (top=2 > bottom=1), traversal complete

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	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
Visited Elements	[]	[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 'top' boundary after traversing the top row?

Because after visiting the top row, that row is fully processed and should not be visited again. Updating 'top' moves the boundary down, as shown in execution_table step 2.

Why does the traversal stop when 'top' becomes greater than 'bottom'?

Because it means all rows have been visited. The boundaries crossed, so no more elements remain inside the current boundaries. This is shown in execution_table step 7.

Why do we traverse the left column from bottom to top instead of top to bottom?

To maintain the spiral order. After traversing bottom row right to left, we go up the left column to complete the outer layer before moving inward, as shown in execution_table step 5.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'right' after step 3?

A 1

B 2

C 0

D 3

💡 Hint

Check the 'Pointer Changes' column in step 3 where right boundary is updated.

At which step does the traversal visit the element '5'?

A Step 5

B Step 6

C Step 4

D Step 7

💡 Hint

Look at the 'Elements visited' column in execution_table for step 6.

If the matrix had 4 columns instead of 3, which boundary would be updated last in the first full spiral cycle?

A top

B bottom

C left

D right

💡 Hint

Refer to the concept_flow where left boundary is updated after traversing left column.

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 edge, update the corresponding boundary inward
- Repeat until boundaries cross (top > bottom or left > right)
- Visits all elements in spiral order without repeats

Full Transcript

Spiral Matrix Traversal uses four boundaries to track the current edges of the matrix to visit. We start with top row from left to right, then right column top to bottom, bottom row right to left, and left column bottom to top. After each edge traversal, we move the boundary inward to avoid revisiting elements. This repeats until the top boundary crosses the bottom or the left crosses the right, meaning all elements have been visited. The execution table shows each step with visited elements and boundary updates. Key moments clarify why boundaries move and when traversal stops. The visual quiz tests understanding of boundary updates and element visits.

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 from outer to inner layers

Solution

1. Step 1: Understand traversal pattern

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

2. Step 2: Compare options

   Only Traverse the matrix in a circular pattern from outer to inner layers 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 from outer to inner layers -> Option D

4. Quick Check:

   Spiral traversal = circular outer to inner [OK]

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

Common Mistakes:

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

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

easy

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

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

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

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

Solution

1. Step 1: Identify correct boundary initialization

   For spiral traversal, top starts at 0, bottom at last row (m-1), left at 0, right at last column (n-1).

2. Step 2: Match with options

   int top = 0, bottom = m-1, left = 0, right = n-1; matches this initialization exactly; others swap or mix row and column indices incorrectly.

3. Final Answer:

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

4. Quick Check:

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

Hint: Top and left start at 0; bottom and right at max index [OK]

Common Mistakes:

• Swapping m and n in bottom or right
• Starting top or left at max index
• Confusing row and column boundaries

3. What is the output of the following C code snippet for spiral traversal of a 3x3 matrix?

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++) printf("%d ", matrix[top][i]);
  top++;
  for(int i=top; i<=bottom; i++) printf("%d ", matrix[i][right]);
  right--;
  if(top <= bottom) {
    for(int i=right; i>=left; i--) printf("%d ", matrix[bottom][i]);
    bottom--;
  }
  if(left <= right) {
    for(int i=bottom; i>=top; i--) printf("%d ", matrix[i][left]);
    left++;
  }
}

medium

A. 1 4 7 8 9 6 3 2 5

B. 1 2 3 6 9 8 7 4 5

C. 1 2 3 4 5 6 7 8 9

D. 1 3 5 7 9 2 4 6 8

Solution

1. Step 1: Trace first outer layer traversal

   Top row left to right: 1 2 3; then right column top to bottom: 6 9; bottom row right to left: 8 7; left column bottom to top: 4.

2. Step 2: Move inward and print center

   Now top=1, bottom=1, left=1, right=1; print center element matrix[1][1] = 5.

3. Final Answer:

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

4. Quick Check:

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

Hint: Follow boundaries and print edges clockwise [OK]

Common Mistakes:

• Skipping center element
• Mixing row and column indices
• Not updating boundaries correctly

4. Find the error in this spiral traversal code snippet for a 3x3 matrix:

int top=0, bottom=2, left=0, right=2;
while(top < bottom && left < right) {
  for(int i=left; i<=right; i++) printf("%d ", matrix[top][i]);
  top++;
  for(int i=top; i<=bottom; i++) printf("%d ", matrix[i][right]);
  right--;
  for(int i=right; i>=left; i--) printf("%d ", matrix[bottom][i]);
  bottom--;
  for(int i=bottom; i>=top; i--) printf("%d ", matrix[i][left]);
  left++;
}

medium

A. The variables top and bottom are swapped

B. The for loops should use < instead of <=

C. The while loop condition should use <= instead of <

D. The matrix indices are accessed incorrectly

Solution

1. Step 1: Analyze loop condition

   The condition top < bottom && left < right stops before the center element is processed in odd-sized matrices.

2. Step 2: Correct condition for full traversal

   Using <= allows the loop to run when top equals bottom or left equals right, ensuring center elements are included.

3. Final Answer:

   The while loop condition should use <= instead of < -> Option C

4. Quick Check:

   Use <= in while condition for complete spiral [OK]

Hint: Use <= in while to include center elements [OK]

Common Mistakes:

• Stopping traversal too early
• Changing for loop bounds incorrectly
• Swapping top and bottom variables

5. Given a 4x4 matrix:

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

Write the spiral traversal output if you start from the bottom-left corner and move clockwise inward.

hard

A. 13 9 5 1 2 3 4 8 12 16 15 14 10 6 7 11

B. 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10

C. 13 14 15 16 12 8 4 3 2 1 5 9 10 11 7 6

D. 16 15 14 13 9 5 1 2 3 4 8 12 11 10 6 7

Solution

1. Step 1: Understand starting point and direction

   Start at bottom-left (matrix[3][0] = 13) and move clockwise: up, right, down, left, inward.

2. Step 2: Trace spiral clockwise from bottom-left

   Up column: 13 9 5 1; right row: 2 3 4; down column: 8 12 16; left row: 15 14 10 6; then inner spiral: 7 11.

3. Final Answer:

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

4. Quick Check:

   Start bottom-left clockwise spiral = 13 9 5 1 2 3 4 8 12 16 15 14 10 6 7 11 [OK]

Hint: Change start and direction, then trace edges inward [OK]

Common Mistakes:

• Starting from top-left instead of bottom-left
• Moving counter-clockwise instead of clockwise
• Mixing row and column indices