Skip to content

2.22 Spiral Traversal

Spiral traversal visits a matrix layer by layer, moving right across the top row, down the right column, left across the bottom row, and up the left column,...

algorithms computer-science arrays strings

Spiral traversal visits a matrix layer by layer, moving right across the top row, down the right column, left across the bottom row, and up the left column, then shrinking the boundaries and repeating.

Problem

Given a matrix:

1 2 3
4 5 6
7 8 9

Spiral order:

1, 2, 3, 6, 9, 8, 7, 4, 5

Boundaries

Maintain four boundaries:

top, bottom, left, right

Initialize:

top = 0
bottom = rows - 1
left = 0
right = cols - 1

At each step, traverse one side and shrink the corresponding boundary.

Implementation 

func SpiralOrder(a [][]int) []int {
	rows := len(a)
	if rows == 0 {
		return nil
	}
	cols := len(a[0])

	top, bottom := 0, rows-1
	left, right := 0, cols-1

	var out []int

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

		for c := left; c <= right; c++ {
			out = append(out, a[top][c])
		}
		top++

		for r := top; r <= bottom; r++ {
			out = append(out, a[r][right])
		}
		right--

		if top <= bottom {
			for c := right; c >= left; c-- {
				out = append(out, a[bottom][c])
			}
			bottom--
		}

		if left <= right {
			for r := bottom; r >= top; r-- {
				out = append(out, a[r][left])
			}
			left++
		}
	}

	return out
}

Invariant 

At the start of each iteration:
- All elements outside the current boundaries have been visited
- The remaining submatrix is defined by rows [top, bottom] and columns [left, right]

Each loop removes one outer layer.

Example Walkthrough

Matrix:

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

Steps:

Top row:      1 2 3 4
Right column: 8 12
Bottom row:   11 10 9
Left column:  5
Next layer:   6 7

Result:

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

Edge Cases

Single row:

1 2 3 → 1 2 3

Single column:

1
2
3 → 1 2 3

The boundary checks:

if top <= bottom
if left <= right

prevent double traversal.

Spiral Matrix Generation

The same pattern can generate a matrix.

func SpiralFill(n int) [][]int {
	a := make([][]int, n)
	for i := range a {
		a[i] = make([]int, n)
	}

	top, bottom := 0, n-1
	left, right := 0, n-1

	val := 1

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

		for c := left; c <= right; c++ {
			a[top][c] = val
			val++
		}
		top++

		for r := top; r <= bottom; r++ {
			a[r][right] = val
			val++
		}
		right--

		if top <= bottom {
			for c := right; c >= left; c-- {
				a[bottom][c] = val
				val++
			}
			bottom--
		}

		if left <= right {
			for r := bottom; r >= top; r-- {
				a[r][left] = val
				val++
			}
			left++
		}
	}

	return a
}

Complexity 

Time:  O(rows * cols)
Space: O(1) extra (excluding output)

Each element is visited exactly once.

Common Pitfalls

Forgetting boundary checks causes duplicates in single-row or single-column cases.

Incorrect loop conditions lead to skipping inner layers.

Mixing < and <= breaks edge handling.

Not updating boundaries after traversal leads to infinite loops.

Design Pattern

Spiral traversal follows:

  1. Maintain shrinking boundaries
  2. Traverse edges in fixed order
  3. Update boundaries after each pass
  4. Stop when boundaries cross

Takeaway

Spiral traversal is boundary-driven iteration over a matrix. It reduces the problem to repeatedly peeling outer layers. Correctness depends on maintaining valid boundaries and avoiding duplicate visits in degenerate cases.