Example 1
ready- Input
matrix = [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ]- Expected
[ 1, 2, 3, 6, 9, 8, 7, 4, 5 ]- Why
- the outer ring comes first, followed by the center
Spiral Matrix
35 min · spiralOrder()mediumOpen in LeetCode #54 ↗
Imagine tracing the edge of a photo, then tracing the smaller photo left inside it.
Given an m x n integer matrix, return every value in spiral order. Start at the
top-left cell, move right across the top, down the right side, left across the bottom,
and up the left side. Keep turning inward until every cell appears exactly once.
Your result is one flat array. The same movement rules apply to square, wide, tall, single-row, and single-column matrices.
Constraints
1 <= m, n <= 100matrixhas exactlymrows, and every row has exactlynvalues.-1_000 <= matrix[i][j] <= 1_000
Hints
Simulate the walk
Track visited cells and keep one of four directions: right, down, left, up. Turn clockwise whenever the next cell is outside the matrix or already visited.
Peel one ring at a time
The unvisited rectangle has four edges: top, right, bottom, and left. Traverse those edges in order, then move every edge one step inward.
Guard the thin leftovers
After crossing the top and right edges, check that a bottom row or left column still remains before traversing it. Those guards prevent duplicates in a single row or single column.
Follow-up
Can you produce the order with O(1) extra working space beyond the returned array?
Visible cases
Examples
Example 2
ready- Input
matrix = [ [ 1, 2, 3, 4 ], [ 5, 6, 7, 8 ], [ 9, 10, 11, 12 ] ]- Expected
[ 1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7 ]- Why
- the same clockwise turns work on a wide rectangle
Example 3
ready- Input
matrix = [ [ 5, 6 ], [ 7, 8 ] ]- Expected
[ 5, 6, 8, 7 ]- Why
- a 2×2 matrix is one complete outer ring
Interview signal
Asked at
AmazonGoogleMicrosoft
Visited-grid simulation
Walk as the prompt describes. A second boolean grid remembers which cells have already joined the result. Before each move, inspect the next position. If it's outside the matrix or already visited, rotate the direction clockwise.
def spiral_order(matrix: list[list[int]]) -> list[int]:
rows, cols = len(matrix), len(matrix[0])
visited = [[False] * cols for _ in range(rows)]
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
row = 0
col = 0
direction = 0
order: list[int] = []
for _ in range(rows * cols):
order.append(matrix[row][col])
visited[row][col] = True
row_step, col_step = directions[direction]
next_row = row + row_step
next_col = col + col_step
blocked = (
next_row < 0
or next_row >= rows
or next_col < 0
or next_col >= cols
or visited[next_row][next_col]
)
if blocked:
direction = (direction + 1) % 4
row_step, col_step = directions[direction]
row += row_step
col += col_step
return orderTime O(m·n) — every cell is visited once. Space O(m·n) for the boolean grid, excluding the returned array.
Shrinking boundaries
The unvisited cells always form a rectangle. Store its four boundaries — the first and last unvisited rows and columns. Read the top edge, right edge, bottom edge, and left edge, then shrink the rectangle.
def spiral_order(matrix: list[list[int]]) -> list[int]:
top = 0
bottom = len(matrix) - 1
left = 0
right = len(matrix[0]) - 1
order: list[int] = []
while top <= bottom and left <= right:
for col in range(left, right + 1):
order.append(matrix[top][col])
top += 1
for row in range(top, bottom + 1):
order.append(matrix[row][right])
right -= 1
if top <= bottom:
for col in range(right, left - 1, -1):
order.append(matrix[bottom][col])
bottom -= 1
if left <= right:
for row in range(bottom, top - 1, -1):
order.append(matrix[row][left])
left += 1
return orderThe two inner guards are what make thin matrices work. Without them, the last remaining row or column gets appended twice.
Time O(m·n) — each cell enters the result once. Space O(1) beyond the returned array.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
[ 1, 2, 3, 6, 9, 8, 7, 4, 5 ]
Run: visible + custom · Submit: full suite