Matrix Spiral Traversal

Before we start

By the end of this page you will be able to:

• See a 2D matrix as a set of concentric rectangular layers, like an onion.
• Explain out loud why tracking four shrinking boundaries guarantees you never revisit a cell.
• Recognise this skeleton in spiral order, rotate image, and spiral generation problems.

Stop at every Pause & Think box — predict before you read ahead.

Picture this first (no code yet)

Every spiral traversal problem is just this chocolate-box process — track the four walls of the current ring, eat them clockwise, shrink the walls inward, repeat.

The actual problem

Given an m × n matrix, return all its elements in spiral (clockwise) order.

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

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

The path: right across the top → down the right → left across the bottom → up the left → then the inner ring → done.

First, the slow way (so you feel the pain)

A common first attempt: mark visited cells with a boolean array, follow the spiral direction, and turn when you hit a wall or a visited cell.

# Direction-following with visited array — messy
directions = [(0,1),(1,0),(0,-1),(-1,0)]  # right, down, left, up
visited = [[False]*n for _ in range(m)]
r, c, d = 0, 0, 0
result = []
for _ in range(m * n):
    result.append(matrix[r][c])
    visited[r][c] = True
    nr, nc = r + directions[d][0], c + directions[d][1]
    if 0 <= nr < m and 0 <= nc < n and not visited[nr][nc]:
        r, c = nr, nc
    else:
        d = (d + 1) % 4
        r, c = r + directions[d][0], c + directions[d][1]

This works but:

• Uses an O(m×n) extra boolean matrix.
• The turning logic is fragile — easy to introduce off-by-one bugs.
• It's hard to extend (e.g., to generate a spiral, not just read one).

The boundary-shrinking approach uses O(1) extra space and is far easier to reason about.

The turning point

Every spiral can be broken into four straight-line walks:

1. Left → Right across the top row
2. Top → Bottom down the right column
3. Right → Left across the bottom row
4. Bottom → Top up the left column

After all four walks, the outermost ring is consumed. The next ring starts exactly one step inward from every boundary.

A 3×3 matrix's outer ring leaves a 1×1 centre — one cell, visited in a degenerate "top row" walk of length 1. A 4×4 matrix's outer ring leaves a 2×2 inner box. In general, each ring reduces both dimensions by 2 (one from each side). The process stops when top > bottom or left > right.

The one idea to remember

Watch it happen, frame by frame

Matrix:

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

Initial boundaries: top=0, bottom=2, left=0, right=2.

Ring 1:

  Walk top row (left→right, row=top=0):
    collect 1, 2, 3.    top += 1  →  top=1

  Walk right column (top→bottom, col=right=2):
    collect 6, 9.       right -= 1 →  right=1

  Walk bottom row (right→left, row=bottom=2):
    collect 8, 7.       bottom -= 1 → bottom=1

  Walk left column (bottom→top, col=left=0):
    collect 4.          left += 1  →  left=1

Remaining box: top=1, bottom=1, left=1, right=1  (a single cell)

Ring 2:

  Walk top row (left→right, row=1):
    collect 5.          top += 1  →  top=2

  top(2) > bottom(1) → stop.

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

[ [1,  2,  3,  4],
  [5,  6,  7,  8],
  [9, 10, 11, 12],
  [13,14, 15, 16] ]

Ring 1: top=0,bot=3,left=0,right=3
  Top row:    1,2,3,4      → top=1
  Right col:  8,12,16      → right=2
  Bottom row: 15,14,13     → bottom=2
  Left col:   9,5          → left=1

Ring 2: top=1,bot=2,left=1,right=2
  Top row:    6,7          → top=2
  Right col:  11           → right=1
  Bottom row: 10           → bottom=1
  Left col:   (top>bottom, skip)

Result: [1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10]  ✅

Now, the code — line by line

def spiralOrder(matrix):
    result = []
    top, bottom = 0, len(matrix) - 1       # top and bottom row boundaries
    left, right = 0, len(matrix[0]) - 1    # left and right column boundaries

    while top <= bottom and left <= right:

        # Walk top row: left → right
        for col in range(left, right + 1):
            result.append(matrix[top][col])
        top += 1                            # top ring consumed — shrink inward

        # Walk right column: top → bottom
        for row in range(top, bottom + 1):
            result.append(matrix[row][right])
        right -= 1                          # right ring consumed — shrink inward

        # Walk bottom row: right → left (only if a bottom row still exists)
        if top <= bottom:
            for col in range(right, left - 1, -1):
                result.append(matrix[bottom][col])
            bottom -= 1                     # bottom ring consumed — shrink inward

        # Walk left column: bottom → top (only if a left column still exists)
        if left <= right:
            for row in range(bottom, top - 1, -1):
                result.append(matrix[row][left])
            left += 1                       # left ring consumed — shrink inward

    return result

Key lines explained:

• top, bottom, left, right — the four walls of the current chocolate box.
• while top <= bottom and left <= right: — there is still box left to unwrap.
• top += 1 after the top-row walk — that row is consumed; next ring starts one row lower.
• if top <= bottom: before the bottom-row walk — after top += 1, the box might have collapsed into a single row. Guard against walking the same row twice.
• if left <= right: before the left-column walk — same guard for a single-column remainder.

Why does it always terminate and never revisit?

Each complete ring shrinks all four boundaries by 1 (top++, bottom--, left++, right--). The box shrinks by 2 in each dimension per ring. For an m × n matrix, there are at most min(m, n) / 2 complete rings (plus one final row or column if a dimension is odd). When top > bottom or left > right, the box is empty — the loop exits.

Every cell is visited exactly once: the four walks in each ring cover the four edges without overlap. Each boundary change immediately prevents revisiting those cells.

Time: O(m × n) — every cell visited exactly once. Space: O(1) — only four boundary integers (output array excluded).

When should I reach for this? (the trigger list)

Reach for layer-by-layer boundary shrinking when:

• Asked to traverse, print, or collect a 2D matrix in spiral or layer order.
• Asked to rotate a matrix (rotation is rearranging layers).
• Asked to generate a spiral matrix (fill instead of read).
• The problem mentions "outermost ring," "peeling," "clockwise/anticlockwise order."

The same trick in three disguises

Disguise 1 — Spiral Matrix II: Generate (LC #59)

Instead of reading from a matrix, write 1, 2, 3, …, n² into an empty matrix in spiral order. Identical four-boundary loop — just assign instead of append.

def generateMatrix(n):
    matrix = [[0] * n for _ in range(n)]
    top, bottom, left, right = 0, n-1, 0, n-1
    num = 1

    while top <= bottom and left <= right:
        for col in range(left, right + 1):
            matrix[top][col] = num; num += 1
        top += 1
        for row in range(top, bottom + 1):
            matrix[row][right] = num; num += 1
        right -= 1
        if top <= bottom:
            for col in range(right, left - 1, -1):
                matrix[bottom][col] = num; num += 1
            bottom -= 1
        if left <= right:
            for row in range(bottom, top - 1, -1):
                matrix[row][left] = num; num += 1
            left += 1

    return matrix

Same skeleton. Only append → assign.

Disguise 2 — Rotate Image (LC #48)

Rotate an n×n matrix 90° clockwise in-place. Strategy: transpose (swap matrix[i][j] with matrix[j][i]), then reverse each row. No boundary loop needed — but the insight is the same layer-based thinking.

def rotate(matrix):
    n = len(matrix)
    # Transpose
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    # Reverse each row
    for row in matrix:
        row.reverse()

def rotate_explicit(matrix):
    n = len(matrix)
    for layer in range(n // 2):
        first, last = layer, n - 1 - layer
        for i in range(first, last):
            offset = i - first
            top = matrix[first][i]
            # left → top
            matrix[first][i] = matrix[last - offset][first]
            # bottom → left
            matrix[last - offset][first] = matrix[last][last - offset]
            # right → bottom
            matrix[last][last - offset] = matrix[first + offset][last]
            # top → right
            matrix[first + offset][last] = top

Traps that catch beginners

Say it like a pro (interview one-liner)

"I'll track four boundaries — top, bottom, left, right — and walk the four edges of the current ring clockwise. After each walk I shrink the corresponding boundary inward. The loop exits when top exceeds bottom or left exceeds right, guaranteeing every cell is visited exactly once in O(m×n) time and O(1) extra space."

while top <= bottom and left <= right:
    walk top row → top++
    walk right col → right--
    if top <= bottom: walk bottom row → bottom--
    if left <= right: walk left col → left++

Check yourself

Practice problems

When you can write the four-boundary loop from memory — including both guards — without peeking, you've learned this pattern.

Next up: Matrix Diagonal Traversal — where we collect cells along anti-diagonals and learn to index them with a single integer key.