Spiral Matrix Traversal in DSA Go

Mental Model

We move around the edges of the matrix in a circle, peeling off layers until all elements are visited.

Analogy: Imagine peeling an onion layer by layer, starting from the outer skin and moving inward in a spiral path.

1 -> 2 -> 3 -> 4
↓           ↑
12         5
↓           ↑
11 10  9 -> 6
     ↑     ↓
     8 ← 7

Dry Run Walkthrough

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

Goal: Print elements in spiral order: 1 -> 2 -> 3 -> 6 -> 9 -> 8 -> 7 -> 4 -> 5

Step 1: Traverse top row from left to right

Visited: 1 -> 2 -> 3
Remaining matrix:
[4,5,6]
[7,8,9]

Why: Start from the top edge to begin the spiral

Step 2: Traverse right column from top to bottom

Visited: 1 -> 2 -> 3 -> 6 -> 9
Remaining matrix:
[4,5]
[7,8]

Why: Move down the right edge after top row

Step 3: Traverse bottom row from right to left

Visited: 1 -> 2 -> 3 -> 6 -> 9 -> 8 -> 7
Remaining matrix:
[4,5]

Why: Move left along the bottom edge

Step 4: Traverse left column from bottom to top

Visited: 1 -> 2 -> 3 -> 6 -> 9 -> 8 -> 7 -> 4
Remaining matrix:
[5]

Why: Move up the left edge to complete the outer layer

Step 5: Traverse the remaining middle element

Visited: 1 -> 2 -> 3 -> 6 -> 9 -> 8 -> 7 -> 4 -> 5
Remaining matrix: empty

Why: Visit the last center element after peeling outer layers

Result:

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

Annotated Code

DSA Go

package main

import "fmt"

func spiralOrder(matrix [][]int) []int {
    if len(matrix) == 0 || len(matrix[0]) == 0 {
        return []int{}
    }
    top, bottom := 0, len(matrix)-1
    left, right := 0, len(matrix[0])-1
    result := []int{}

    for left <= right && top <= bottom {
        // Traverse from left to right on top row
        for col := left; col <= right; col++ {
            result = append(result, matrix[top][col])
        }
        top++ // move top boundary down

        // Traverse from top to bottom on right column
        for row := top; row <= bottom; row++ {
            result = append(result, matrix[row][right])
        }
        right-- // move right boundary left

        if top <= bottom {
            // Traverse from right to left on bottom row
            for col := right; col >= left; col-- {
                result = append(result, matrix[bottom][col])
            }
            bottom-- // move bottom boundary up
        }

        if left <= right {
            // Traverse from bottom to top on left column
            for row := bottom; row >= top; row-- {
                result = append(result, matrix[row][left])
            }
            left++ // move left boundary right
        }
    }
    return result
}

func main() {
    matrix := [][]int{
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9},
    }
    result := spiralOrder(matrix)
    for i, val := range result {
        if i > 0 {
            fmt.Print(" -> ")
        }
        fmt.Print(val)
    }
    fmt.Println()
}

for left <= right && top <= bottom {

continue while there are layers to traverse

for col := left; col <= right; col++ { result = append(result, matrix[top][col]) }

traverse top row left to right

top++

move top boundary down after visiting top row

for row := top; row <= bottom; row++ { result = append(result, matrix[row][right]) }

traverse right column top to bottom

right--

move right boundary left after visiting right column

if top <= bottom { for col := right; col >= left; col-- { result = append(result, matrix[bottom][col]) } bottom-- }

traverse bottom row right to left if still valid

if left <= right { for row := bottom; row >= top; row-- { result = append(result, matrix[row][left]) } left++ }

traverse left column bottom to top if still valid

Output

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

Complexity Analysis

Time: O(m*n) because every element in the m by n matrix is visited exactly once

Space: O(m*n) for the output list storing all elements

vs Alternative: Compared to naive repeated scanning, this approach visits each element once in a controlled spiral, avoiding repeated visits and extra checks

Edge Cases

empty matrix

returns empty list immediately

DSA Go

if len(matrix) == 0 || len(matrix[0]) == 0 { return []int{} }

single row matrix

traverses left to right only

DSA Go

for col := left; col <= right; col++ { result = append(result, matrix[top][col]) }

single column matrix

traverses top to bottom only

DSA Go

for row := top; row <= bottom; row++ { result = append(result, matrix[row][right]) }

When to Use This Pattern

When you need to visit all elements of a matrix in a circular, shrinking pattern, use spiral traversal to peel layers one by one.

Common Mistakes

Mistake: Not updating boundaries correctly causing infinite loops or repeated elements
Fix: After each edge traversal, update the corresponding boundary (top, bottom, left, right) to shrink the matrix layer

Mistake: Not checking boundary conditions before traversing bottom row or left column
Fix: Add checks like if top <= bottom and if left <= right before those traversals to avoid duplicates

Summary

Prints matrix elements in a spiral order starting from the top-left corner.

Use when you want to read or print matrix elements layer by layer in a circular pattern.

The key is to keep track of four boundaries and move them inward after each edge traversal.

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