Spiral Matrix Traversal in DSA Go - Time & Space Complexity

Time Complexity: Spiral Matrix Traversal

O(n * m)

Understanding Time Complexity

We want to understand how the time needed to traverse a matrix in a spiral grows as the matrix size increases.

How does the number of steps change when the matrix gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

    for left <= right && top <= bottom {
        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--
        if top <= bottom {
            for i := right; i >= left; i-- {
                result = append(result, matrix[bottom][i])
            }
            bottom--
        }
        if left <= right {
            for i := bottom; i >= top; i-- {
                result = append(result, matrix[i][left])
            }
            left++
        }
    }
    return result
}
    

This code collects all elements of a 2D matrix in a spiral order starting from the top-left corner.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Visiting each element of the matrix exactly once.
• How many times: Each element is visited once in the spiral traversal loops.

How Execution Grows With Input

As the matrix size grows, the number of elements to visit grows too.

Input Size (n x n)	Approx. Operations
10 x 10	100 visits
100 x 100	10,000 visits
1000 x 1000	1,000,000 visits

Pattern observation: The operations grow roughly with the total number of elements, which is the square of the matrix dimension.

Final Time Complexity

Time Complexity: O(n * m)

This means the time grows proportionally to the total number of elements in the matrix, where n and m are the matrix dimensions.

Common Mistake

[X] Wrong: "The spiral traversal has nested loops that multiply to O(n²) even for non-square matrices."

[OK] Correct: Each element is visited only once, so the total steps equal the number of elements, not the square of dimensions.

Interview Connect

Understanding this traversal helps you think about how to visit all parts of a structure efficiently, a skill useful in many coding problems.

Self-Check

"What if the matrix is not rectangular but jagged (rows have different lengths)? How would the time complexity change?"

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