Spiral Matrix Traversal in DSA Go - 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

↓

Repeat or End

We keep four boundaries and move inward in a spiral: top row left→right, right column top→bottom, bottom row right→left, left column bottom→top, then repeat until all elements are visited.

Execution Sample

DSA Go

top, bottom := 0, rows-1
left, right := 0, cols-1
for top <= bottom && left <= right {
  // Traverse top row
  for i := left; i <= right; i++ {
    result = append(result, matrix[top][i])
  }
  top++
  // Traverse right column
  for i := top; i <= bottom; i++ {
    result = append(result, matrix[i][right])
  }
  right--
  // Traverse bottom row
  if top <= bottom {
    for i := right; i >= left; i-- {
      result = append(result, matrix[bottom][i])
    }
    bottom--
  }
  // Traverse left column
  if left <= right {
    for i := bottom; i >= top; i-- {
      result = append(result, matrix[i][left])
    }
    left++
  }
}

This code visits matrix elements in a spiral order by adjusting boundaries after each side traversal.

Execution Table

Step	Operation	Boundaries (top,bottom,left,right)	Elements Added	Visual State (Spiral Order)
1	Traverse top row left→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→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→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→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→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 top <= bottom and left <= right	(2,1,1,1)	[]	[1, 2, 3, 6, 9, 8, 7, 4, 5]

💡 top (2) > bottom (1), loop ends because all elements are visited

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
result	[]	[1,2,3]	[1,2,3,6,9]	[1,2,3,6,9,8,7,4]	[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 'if top <= bottom' before traversing the bottom row?

Because after moving the top boundary down, top might cross bottom. If we don't check, we could add elements twice or go out of bounds. See execution_table row 5 where this check prevents errors.

Why do we update boundaries after each side traversal?

Updating boundaries moves the spiral inward, preventing revisiting elements. For example, after traversing the top row (row 0), top moves from 0 to 1 (row 1) as shown in execution_table rows 1 and 2.

When does the loop stop?

The loop stops when top > bottom or left > right, meaning all layers are traversed. In execution_table row 11, top=2 and bottom=1, so loop ends.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, which elements are added?

A [4]

B [8, 7]

C [6, 9]

D [1, 2, 3]

💡 Hint

Check the 'Elements Added' column at step 3 in execution_table.

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

A Step 6

B Step 8

C Step 4

D Step 10

💡 Hint

Look at the 'Boundaries' column changes in variable_tracker for 'left'.

If the matrix had one more row, how would the exit condition change?

A Loop would stop later because bottom boundary is larger

B Loop would stop earlier because top boundary moves faster

C Loop would never stop

D Loop stops at the same step

💡 Hint

Consider how bottom boundary affects the loop condition top <= bottom in execution_table exit_note.

Concept Snapshot

Spiral Matrix Traversal:
- Use four boundaries: top, bottom, left, right
- Traverse top row left→right, then move top++
- Traverse right column top→bottom, then move right--
- Traverse bottom row right→left if top <= bottom, then bottom--
- Traverse left column bottom→top if left <= right, then left++
- Repeat until boundaries cross (top > bottom or left > right)

Full Transcript

Spiral Matrix Traversal visits all elements of a matrix in a spiral order starting from the top-left corner. We keep track of 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, if the top boundary is still less than or equal to the bottom, we traverse the bottom row from right to left and move the bottom boundary up. After that, if the left boundary is still less than or equal to the right, we traverse the left column from bottom to top and move the left boundary right. We repeat these steps until the boundaries cross, meaning all elements have been visited. This method ensures we visit every element exactly once in a spiral pattern.

Practice

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

easy

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

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

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

D. Traverse only the diagonal elements of the matrix

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 with spiral pattern

   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 A

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 Go code snippets correctly initializes the boundaries for spiral traversal of a matrix named matrix?

easy

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

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

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

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

Solution

1. Step 1: Identify correct boundary initialization

   For spiral traversal, top and left start at 0, bottom and right are last indices (length - 1).

2. Step 2: Check each option

   top, bottom := 0, len(matrix)-1; left, right := 0, len(matrix[0])-1 correctly sets top=0, bottom=len(matrix)-1, left=0, right=len(matrix[0])-1. Others have off-by-one or negative values.

3. Final Answer:

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

4. Quick Check:

   Boundaries start at 0 and end at length-1 [OK]

Hint: Remember Go slices are 0-indexed, so last index is length-1 [OK]

Common Mistakes:

• Using length instead of length-1 for boundaries
• Starting boundaries at 1 instead of 0
• Using negative indices incorrectly

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

matrix := [][]int{
  {1, 2, 3},
  {4, 5, 6},
  {7, 8, 9},
}
result := []int{}
top, bottom := 0, 2
left, right := 0, 2
for top <= bottom && left <= right {
  for i := left; i <= right; i++ {
    result = append(result, matrix[top][i])
  }
  top++
  for i := top; i <= bottom; i++ {
    result = append(result, matrix[i][right])
  }
  right--
  for i := right; i >= left; i-- {
    result = append(result, matrix[bottom][i])
  }
  bottom--
  for i := bottom; i >= top; i-- {
    result = append(result, matrix[i][left])
  }
  left++
}
fmt.Println(result)

medium

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

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

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

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

Solution

1. Step 1: Trace the spiral traversal steps

   Traverse top row left to right: 1,2,3; then right column top to bottom: 6,9; then bottom row right to left: 8,7; then left column bottom to top: 4; then inner layer top row: 5.

2. Step 2: Collect elements in order

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

3. Final Answer:

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

4. Quick Check:

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

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

Common Mistakes:

• Not updating boundaries correctly after each loop
• Repeating elements or missing inner elements
• Confusing row and column indices

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

top, bottom := 0, len(matrix)
left, right := 0, len(matrix[0])
for top <= bottom && left <= right {
  for i := left; i <= right; i++ {
    fmt.Print(matrix[top][i], " ")
  }
  top++
  // ... rest of traversal
}

medium

A. Missing initialization of top and left variables

B. Using len(matrix) and len(matrix[0]) instead of len(matrix)-1 and len(matrix[0])-1 for boundaries

C. Incorrect loop condition using <= instead of <

D. Using fmt.Print instead of fmt.Println

Solution

1. Step 1: Check boundary initialization

   len(matrix) gives count, but last index is len(matrix)-1. Using len(matrix) causes out-of-range error.

2. Step 2: Confirm loop indices

   Loop uses i <= right, so right must be last valid index, not length.

3. Final Answer:

   Using len(matrix) and len(matrix[0]) instead of len(matrix)-1 and len(matrix[0])-1 for boundaries -> Option B

4. Quick Check:

   Boundaries must be last index = length-1 [OK]

Hint: Remember last index is length minus one [OK]

Common Mistakes:

• Setting boundaries to length instead of length-1
• Looping beyond matrix size causing runtime error
• Ignoring zero-based indexing

5. Given a rectangular matrix:

matrix := [][]int{
  {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 5 6 7 0]

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

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

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

Solution

1. Step 1: Traverse top row left to right

   Elements: 1, 2, 3, 4

2. Step 2: Traverse right column top to bottom (excluding top row)

   Elements: 8, 12

3. Step 3: Traverse bottom row right to left (excluding right column)

   Elements: 11, 10, 9

4. Step 4: Traverse left column bottom to top (excluding top and bottom rows)

   Element: 5

5. Step 5: Traverse inner top row left to right

   Elements: 6, 7

6. Final Answer:

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

7. Quick Check:

   Spiral order matches [1 2 3 4 8 12 11 10 9 5 6 7] [OK]

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

Common Mistakes:

• Adding extra elements not in matrix
• Mixing row and column traversal order
• Forgetting to shrink boundaries after each layer