# 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, then shrinking the boundaries and repeating.

## Problem

Given a matrix:

```text id="m1k8ra"
1 2 3
4 5 6
7 8 9
```

Spiral order:

```text id="x4w2ne"
1, 2, 3, 6, 9, 8, 7, 4, 5
```

## Boundaries

Maintain four boundaries:

```text id="v7p3qt"
top, bottom, left, right
```

Initialize:

```text id="d8s0yc"
top = 0
bottom = rows - 1
left = 0
right = cols - 1
```

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

## Implementation

```go id="k6h2mf"
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

```text id="z2t9fq"
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:

```text id="h8p3ls"
1 2 3 4
5 6 7 8
9 10 11 12
```

Steps:

```text id="o6x1md"
Top row:      1 2 3 4
Right column: 8 12
Bottom row:   11 10 9
Left column:  5
Next layer:   6 7
```

Result:

```text id="n9b2wx"
1 2 3 4 8 12 11 10 9 5 6 7
```

## Edge Cases

Single row:

```text id="c3k5zr"
1 2 3 → 1 2 3
```

Single column:

```text id="f1q8uv"
1
2
3 → 1 2 3
```

The boundary checks:

```text id="p0l6na"
if top <= bottom
if left <= right
```

prevent double traversal.

## Spiral Matrix Generation

The same pattern can generate a matrix.

```go id="v3t5eg"
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

```text id="r5k9ht"
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.