The problem
Return every element of an m × n matrix in spiral order: along the top row, down the right side, back along the bottom, up the left, and inwards ring by ring.
Examples
01
- Input
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
- Output
[1, 2, 3, 6, 9, 8, 7, 4, 5]
02
- Input
matrix = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]
- Output
[1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]
Constraints
- 1 ≤ m, n ≤ 10
- −100 ≤ matrix[i][j] ≤ 100
The idea
Keep four walls — top, bottom, left, right — around the part not yet read. Read the ring they enclose: the top row left to right, the right column downwards, the bottom row right to left, the left column upwards. Then move every wall one step in.
The one trap is a last ring only one row or one column thick: reading its bottom and left too would read it twice. So read those two sides only when the ring is more than one thick.
- Time
- O(m · n)
- Space
- O(1) besides the answer
Solution · every language run against every case
class Solution: def spiralOrder(self, matrix: List[List[int]]) -> List[int]: out = [] top, bottom, left, right = 0, len(matrix) - 1, 0, len(matrix[0]) - 1 # the ring still unread while top <= bottom and left <= right: out += matrix[top][left : right + 1] # along the top out += [matrix[r][right] for r in range(top + 1, bottom + 1)] # down the right side if top < bottom and left < right: # a ring more than one row or column thick out += matrix[bottom][left:right][::-1] # back along the bottom out += [matrix[r][left] for r in range(bottom - 1, top, -1)] # up the left side top, bottom, left, right = top + 1, bottom - 1, left + 1, right - 1 return out