124. Spiral Traversal

Why this mechanism works

Peel one perimeter at a time. Four half-open boundaries describe the remaining rectangle. After consuming an edge, move its boundary inward before traversing the next edge. Recheck whether a bottom row or left column still exists so thin final layers are not visited twice.

State and boundaries

Unvisited cells lie in rows [top,bottom) and columns [left,right). output contains completed perimeter edges in traversal order.

Protocol

1. Traverse and remove the top row.
2. Traverse and remove the right column.
3. If rows remain, traverse and remove the bottom row backward.
4. If columns remain, traverse and remove the left column upward.
5. Repeat while the rectangle is nonempty.

Visualization

top row ->
^         |
|         v
<- bottom row
then shrink all four boundaries

Python implementation

def spiral_order(matrix):
    if not matrix or not matrix[0]:
        return []
    top, bottom = 0, len(matrix)
    left, right = 0, len(matrix[0])
    output = []
    while top < bottom and left < right:
        for c in range(left, right):
            output.append(matrix[top][c])
        top += 1
        for r in range(top, bottom):
            output.append(matrix[r][right - 1])
        right -= 1
        if top < bottom:
            bottom -= 1
            for c in range(right - 1, left - 1, -1):
                output.append(matrix[bottom][c])
        if left < right:
            for r in range(bottom - 1, top - 1, -1):
                output.append(matrix[r][left])
            left += 1
    return output

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 spiral_order: if not matrix or not matrix[0]:
matrix=[[1, 2, 3], [4, 5, 6], [7, 8, 9]]

L4 spiral_order: top, bottom = 0, len(matrix)
matrix=[[1, 2, 3], [4, 5, 6], [7, 8, 9]]; top=0; bottom=3

L5 spiral_order: left, right = 0, len(matrix[0])
matrix=[[1, 2, 3], [4, 5, 6], [7, 8, 9]]; top=0; bottom=3; left=0; right=3

L6 spiral_order: output = []
matrix=[[1, 2, 3], [4, 5, 6], [7, 8, 9]]; top=0; bottom=3; left=0; right=3; output=[]

L8 spiral_order: for c in range(left, right):
matrix=[[1, 2, 3], [4, 5, 6], [7, 8, 9]]; top=0; bottom=3; left=0; right=3; output=[]; c=0

L9 spiral_order: output.append(matrix[top][c])
matrix=[[1, 2, 3], [4, 5, 6], [7, 8, 9]]; top=0; bottom=3; left=0; right=3; output=[1]; c=0

L8 spiral_order: for c in range(left, right):
matrix=[[1, 2, 3], [4, 5, 6], [7, 8, 9]]; top=0; bottom=3; left=0; right=3; output=[1]; c=1

L9 spiral_order: output.append(matrix[top][c])
matrix=[[1, 2, 3], [4, 5, 6], [7, 8, 9]]; top=0; bottom=3; left=0; right=3; output=[1, 2]; c=1

... 16 intermediate state changes omitted ...

L8 spiral_order: for c in range(left, right):
matrix=[[1, 2, 3], [4, 5, 6], [7, 8, 9]]; top=1; bottom=2; left=1; right=2; output=[1, 2, 3, 6, 9, 8, 7, 4]; c=1; r=1

L9 spiral_order: output.append(matrix[top][c])
matrix=[[1, 2, 3], [4, 5, 6], [7, 8, 9]]; top=1; bottom=2; left=1; right=2; output=[1, 2, 3, 6, 9, 8, 7, 4, ...]; c=1; r=1

L10 spiral_order: top += 1
matrix=[[1, 2, 3], [4, 5, 6], [7, 8, 9]]; top=2; bottom=2; left=1; right=2; output=[1, 2, 3, 6, 9, 8, 7, 4, ...]; c=1; r=1

L13 spiral_order: right -= 1
matrix=[[1, 2, 3], [4, 5, 6], [7, 8, 9]]; top=2; bottom=2; left=1; right=1; output=[1, 2, 3, 6, 9, 8, 7, 4, ...]; c=1; r=1

L2 spiral_order: if not matrix or not matrix[0]:
matrix=[[1], [2], [3]]

L4 spiral_order: top, bottom = 0, len(matrix)
matrix=[[1], [2], [3]]; top=0; bottom=3

L5 spiral_order: left, right = 0, len(matrix[0])
matrix=[[1], [2], [3]]; top=0; bottom=3; left=0; right=1

L6 spiral_order: output = []
matrix=[[1], [2], [3]]; top=0; bottom=3; left=0; right=1; output=[]

L8 spiral_order: for c in range(left, right):
matrix=[[1], [2], [3]]; top=0; bottom=3; left=0; right=1; output=[]; c=0

L9 spiral_order: output.append(matrix[top][c])
matrix=[[1], [2], [3]]; top=0; bottom=3; left=0; right=1; output=[1]; c=0

L10 spiral_order: top += 1
matrix=[[1], [2], [3]]; top=1; bottom=3; left=0; right=1; output=[1]; c=0

L11 spiral_order: for r in range(top, bottom):
matrix=[[1], [2], [3]]; top=1; bottom=3; left=0; right=1; output=[1]; c=0; r=1

... 1 intermediate state changes omitted ...

L11 spiral_order: for r in range(top, bottom):
matrix=[[1], [2], [3]]; top=1; bottom=3; left=0; right=1; output=[1, 2]; c=0; r=2

L12 spiral_order: output.append(matrix[r][right - 1])
matrix=[[1], [2], [3]]; top=1; bottom=3; left=0; right=1; output=[1, 2, 3]; c=0; r=2

L13 spiral_order: right -= 1
matrix=[[1], [2], [3]]; top=1; bottom=3; left=0; right=0; output=[1, 2, 3]; c=0; r=2

L15 spiral_order: bottom -= 1
matrix=[[1], [2], [3]]; top=1; bottom=2; left=0; right=0; output=[1, 2, 3]; c=0; r=2

Why the solution is correct

Each edge traversal visits only the current unvisited rectangle, and the boundary update excludes that edge from subsequent traversals. The extra existence checks handle a final single row or column. Repeated peeling therefore visits every cell once in the required order.

Time and space

O(rows*cols) time and O(rows*cols) output space, with O(1) boundary state.

Common mistakes

Updating a boundary after rather than before the next edge can duplicate corner cells. Thin rectangles expose missing existence checks.

Reasoning card

Transfer exercise

Generate an n-by-n spiral matrix filled with 1 through n^2 using the same boundary protocol.