Spiral Matrix

A spiral traversal can look correct on a square matrix and still fail immediately on a single row or column. The reliable model is a shrinking rectangle: track its four inclusive boundaries, consume one side at a time, and guard any side that may have collapsed.

Read the contract and spot the pattern

The task is narrow:

• Input: an m × n rectangular matrix.
• Output: every element exactly once.
• Order: clockwise spiral order, starting at the top-left.
• Direction cycle: right, down, left, up, repeating toward the center.

For example:

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

The spiral order is:

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

The useful pattern signal is structural: after the outer ring is consumed, the unvisited cells still form a rectangle. That rectangle gets smaller after each pass.

This is a matrix boundary traversal, not graph search. We do not need a visited matrix because the boundaries themselves describe which cells remain unvisited.

The required result list already takes O(mn) space. The goal is to use only O(1) additional traversal state.

Why naive simulation repeats cells

The most direct approach is to simulate movement:

1. Start at the top-left.
2. Move in the current direction.
3. Turn clockwise when the next cell is outside the matrix or already visited.
4. Record each cell in a result list.
5. Track visited cells in a boolean matrix.

That approach is valid and often easy to visualize. It touches each cell once, but the visited matrix costs O(mn) auxiliary space.

There is a more dangerous version of the same idea: write four loops for the top row, right column, bottom row, and left column, but omit the conditions that check whether those sides still exist.

Consider a one-row matrix:

1 2 3 4

The top-row pass correctly appends all four values. If the code then blindly runs the bottom-row pass, it walks across the same row in reverse and appends:

4 3 2 1

A one-column matrix creates the same problem vertically. The final “ring” may be only one row, one column, or one cell. The traversal must recognize that collapse instead of treating every pass as a distinct side.

The interview target is therefore:

Keep the clear directional sequence, but encode already-consumed territory with four boundary indices instead of a visited grid.

Track the remaining rectangle

Use four inclusive boundaries:

• top: first unvisited row
• bottom: last unvisited row
• left: first unvisited column
• right: last unvisited column

Initially, the entire matrix is unvisited:

top = 0
bottom = m - 1
left = 0
right = n - 1

The key invariant is:

Before every iteration, all unvisited cells are inside top <= bottom and left <= right. Every cell outside those boundaries has already been appended.

Each iteration consumes the current rectangle in clockwise order.

1. Traverse the top row

Read columns from left through right:

matrix[top][left], matrix[top][left + 1], ..., matrix[top][right]

Then that row is finished:

top += 1

2. Traverse the right column

Read rows from the new top through bottom:

matrix[top][right], matrix[top + 1][right], ..., matrix[bottom][right]

Then that column is finished:

right -= 1

Starting the right-column pass at the updated top prevents the top-right corner from being emitted twice.

3. Traverse the bottom row if it still exists

The top-row pass may have consumed the only remaining row. Only traverse the bottom row when:

top <= bottom

Read from right down to left, then shrink:

bottom -= 1

This guard matters because top > bottom means the remaining height is zero.

4. Traverse the left column if it still exists

The right-column pass may have consumed the only remaining column. Only traverse the left column when:

left <= right

Read from bottom up to top, then shrink:

left += 1

The order of the updates matters. The bottom-row guard comes after top has moved inward. The left-column guard comes after right has moved inward and after the bottom row may have been consumed.

That is the whole algorithm: walk four sides, move four boundaries, repeat.

Implement the Spiral Matrix solution in Python

def spiral_order(matrix: list[list[int]]) -> list[int]:
    if not matrix or not matrix[0]:
        return []

    m = len(matrix)
    n = len(matrix[0])

    result = []

    top = 0
    bottom = m - 1
    left = 0
    right = n - 1

    while top <= bottom and left <= right:
        # Top row: left to right.
        for col in range(left, right + 1):
            result.append(matrix[top][col])
        top += 1

        # Right column: top to bottom.
        for row in range(top, bottom + 1):
            result.append(matrix[row][right])
        right -= 1

        # Bottom row: right to left, only if a row remains.
        if top <= bottom:
            for col in range(right, left - 1, -1):
                result.append(matrix[bottom][col])
            bottom -= 1

        # Left column: bottom to top, only if a column remains.
        if left <= right:
            for row in range(bottom, top - 1, -1):
                result.append(matrix[row][left])
            left += 1

    return result

There are two details I check immediately when writing this in an interview:

1. n must come from len(matrix[0]), not len(matrix). Rectangular matrices can have different row and column counts.
2. The bottom-row and left-column passes are conditional. Those guards are the difference between a boundary traversal and a duplicate-producing loop.

The outer condition:

while top <= bottom and left <= right:

means a valid rectangle remains. Once either dimension collapses, traversal stops.

Prove coverage and no duplication

A solution that matches one square example is not yet a solution. The boundary invariant gives a short correctness argument.

Coverage

At the start of each iteration, every unvisited cell lies inside the current rectangle.

• The top-row pass consumes the rectangle's first row.
• The right-column pass consumes its right edge, excluding the already-consumed top-right corner.
• The bottom-row pass consumes its last row if that row still exists.
• The left-column pass consumes its left edge if that column still exists.

After each pass, the corresponding boundary moves inward. Therefore, the next iteration considers only cells that have not been consumed by an earlier pass.

Because the rectangle shrinks inward, the process eventually reaches every matrix coordinate.

No duplication

The corners are where careless implementations fail.

• The right-column loop starts at top, after the top row has been removed. It does not revisit the top-right corner.
• The bottom-row loop runs only if top <= bottom. If the top pass consumed the last remaining row, the bottom row is skipped.
• The left-column loop runs only if left <= right. If the right-column pass consumed the last remaining column, the left column is skipped.
• Its starting row is the updated bottom, and its ending row is the updated top, so it does not revisit cells already consumed on the bottom row.

The stopping condition proves termination: every complete side moves a boundary inward, and no boundary can move outward.

A useful implementation check is:

len(spiral_order(matrix)) == len(matrix) * len(matrix[0])

That checks coverage count, though not order. To verify order, inspect a rectangular case where row and column values make accidental reversals obvious.

Dry-run rectangular and singleton matrices

A 3 × 4 matrix

Start with:

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

Initial state:

top = 0, bottom = 2, left = 0, right = 3

Pass	Boundaries before pass	Appended values	Updated boundary
Top row	top=0, left=0..3	1, 2, 3, 4	top=1
Right column	right=3, row=1..2	8, 12	right=2
Bottom row	bottom=2, col=2..0	11, 10, 9	bottom=1
Left column	left=0, row=1..1	5	left=1

The remaining rectangle is:

6 7

Its state is:

top = 1, bottom = 1, left = 1, right = 2

The next iteration appends:

6, 7

The final result is:

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

Notice the state, not the picture. The picture helps at first, but the boundaries are what make the code reliable.

A 1 × 4 matrix

1 2 3 4

Initial state:

top = 0, bottom = 0, left = 0, right = 3

The top-row pass appends all four values and changes top to 1.

Now:

top = 1, bottom = 0

No row remains, so the bottom-row guard fails. The left-column guard also fails because right has already moved to 2, but the row range is empty.

Result:

[1, 2, 3, 4]

A 4 × 1 matrix

1
2
3
4

The top-row pass appends 1. The right-column pass then appends 2, 3, 4 from top to bottom.

After that:

right = -1

The left-column guard fails because left <= right is false. The traversal does not walk upward through the same column again.

Result:

[1, 2, 3, 4]

A 3 × 3 matrix

1 2 3
4 5 6
7 8 9

The outer ring produces:

[1, 2, 3, 6, 9, 8, 7, 4]

The remaining rectangle is the single cell 5. The loop processes that one-cell rectangle once:

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

The same guards that handle one row or one column also protect the center of an odd-sized matrix.

Complexity and interview checks

Let m be the number of rows and n the number of columns.

Time

The algorithm is O(mn).

Every matrix element is appended exactly once. The loops are split into four directions, but together they account for the full m × n matrix. Boundary comparisons add constant work per layer and do not change the total bound.

Space

The traversal uses O(1) auxiliary space for:

top, bottom, left, right

The output list requires O(mn) space because the problem explicitly asks us to return every element. When reporting space complexity, distinguish those two facts:

• Auxiliary traversal space: O(1)
• Required output space: O(mn)

Common bugs

Check these before submitting:

• Using the row count for both dimensions.
  Use m = len(matrix) and n = len(matrix[0]).

• Mixing inclusive and exclusive boundaries.
  This implementation uses inclusive top, bottom, left, and right everywhere.

• Forgetting + 1 in an increasing range.
  range(left, right + 1) must include right.

• Forgetting the lower endpoint in a reverse range.
  range(right, left - 1, -1) must include left.

• Updating the wrong boundary.
  Top row consumes top; right column consumes right; bottom row consumes bottom; left column consumes left.

• Omitting one of the two guards.
  The bottom row and left column may no longer be distinct sides.

• Testing only square matrices.
  A square example can hide both dimension mistakes and collapsed-boundary mistakes.

My interview test set is small and deliberate: one rectangular matrix, one single-row matrix, one single-column matrix, and one odd-dimension matrix with a center cell. Read the output. Trace the four boundaries. Fix the assumption exposed by the first failure.

The transferable rule is simple:

When a process peels a rectangular region and completed edges must never be revisited, represent the unprocessed region explicitly. State the boundary invariant first, then guard every side that may have collapsed.

Implement the four-boundary state from that rule—not from memorized loop syntax.