Problem. Return all elements of a matrix in spiral order.
This is the classic layer-by-layer boundary walk pattern.
Examples:
matrix = [[1,2,3],[4,5,6],[7,8,9]]→[1,2,3,6,9,8,7,4,5]matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]→[1,2,3,4,8,12,11,10,9,5,6,7]matrix = [[1]]→[1]
Solution. Track the current top, bottom, left, and right boundaries. Walk one edge at a time and contract the corresponding boundary until the region disappears.
def spiral_order(matrix):
top = 0
bottom = len(matrix) - 1
left = 0
right = len(matrix[0]) - 1
order = []
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 order
O(m * n) time, O(1) extra space besides the output.
Gotchas.
- The two inner boundary checks prevent double-counting when only one row or one column remains.
- This is easier to reason about with explicit top/bottom/left/right names than with direction arrays.
- A jagged matrix is outside the standard problem contract; assume all rows have equal length.