Spiral Matrix

Given an m x n matrix, return all elements in spiral order (clockwise, starting from the top-left).

Why this is worth learning

The unvisited cells remain a rectangle. Boundary variables describe that rectangle, not the original matrix after some edges have already been consumed.

Before coding: one-minute experiment

What is the spiral order of [[1,2,3],[4,5,6]]?

Function signature

func SpiralOrder(matrix [][]int) []int

Inputs / outputs

• matrix: 2D slice of integers.
• Return: slice of elements in spiral order.

Example

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

Constraints

• 0 <= m, n <= 1000
• m*n can be 0.

Core idea (near-solution)

Maintain four boundaries:

• top, bottom, left, right.

At each step, traverse one edge and then shrink that boundary. Stop when the boundaries cross.

Invariant: all elements outside the current boundaries have already been emitted.

Algorithm (step-by-step)

1. Return an empty result if there are no rows or no columns. Otherwise initialize top = 0, bottom = m-1, left = 0, right = n-1.
2. While top <= bottom and left <= right:
   • Traverse top row left->right, then top++.
   • Traverse right column top->bottom, then right--.
   • If top <= bottom, traverse bottom row right->left, then bottom--.
   • If left <= right, traverse left column bottom->top, then left++.
3. Return the collected list.

Correctness sketch

At the start of a round, exactly the cells inside the current bounds remain unvisited. Emit the top edge and remove it, then the right edge and remove it. Emit the bottom edge only if a row remains, and the left edge only if a column remains; updated bounds exclude corners already emitted in this round. These sweeps visit disjoint parts of the current perimeter in clockwise order and leave the smaller interior rectangle. Induction peels every layer exactly once. Empty bounds terminate; in a single remaining row or column the extra guards prevent traversing it again in reverse.

Trace (hand walkthrough)

Example input:
matrix = [
  [1,2,3],
  [4,5,6],
  [7,8,9]
]
Output: [1,2,3,6,9,8,7,4,5]

Walk:
- top row (r=0): 1,2,3
- right col (c=2, r=1..2): 6,9
- bottom row (r=2, c=1..0): 8,7
- left col (c=0, r=1..1): 4
- center: 5 -> [1,2,3,6,9,8,7,4,5]

Pitfalls to avoid

• Forgetting the boundary checks before traversing bottom/left edges.
• Off-by-one when the matrix has one row or one column.

Debugging lens

Use rectangular shapes, one row, one column, and zero columns. Filling each cell with a unique ID catches duplicated or missing corners better than an all-equal matrix.

Complexity

• Time: O(m*n)
• Extra space: O(1) beyond output.

Implementation notes (Go)

• Maintain top, bottom, left, right bounds.
• Check bounds before each sweep to avoid duplicates.

Contract precision

The input is rectangular. Empty outer slices and rectangular zero-column matrices produce an empty result. The matrix is not mutated.

Reconstruction checkpoint

What is the spiral order of [[1,2,3],[4,5,6]]?

Return to Matrix · Module quiz