Description
Read a nonempty rectangular matrix clockwise from the outside inward and return the values.
Solution
def spiral_order(matrix):
top,bottom,left,right = 0,len(matrix)-1,0,len(matrix[0])-1
result = []
while top <= bottom and left <= right:
for c in range(left,right+1):
result.append(matrix[top][c])
top += 1
for r in range(top,bottom+1):
result.append(matrix[r][right])
right -= 1
if top <= bottom:
for c in range(right,left-1,-1):
result.append(matrix[bottom][c])
bottom -= 1
if left <= right:
for r in range(bottom,top-1,-1):
result.append(matrix[r][left])
left += 1
return resultExamples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[[[1,2,3],[4,5,6]]]- Output
[1,2,3,6,5,4]
Read the top, right, then bottom toward the left.
Example 2
- Input
[[[1],[2]]]- Output
[1,2]
A single column is read downward.
Example 3
- Input
[[[9]]]- Output
[9]
The one cell is visited exactly once.
Approach
Maintain four boundaries and peel off a top row, right column, bottom row, and left column.
Time & space
O(R C) time; O(1) auxiliary space excluding output. R and C are the row and column counts.