Given an m x n matrix, return all of its elements in spiral order: go right along the top row, down the right column, left along the bottom row, up the left column, and keep spiralling inwards until every element is visited.
- 1 <= m, n <= 10
- -100 <= matrix[i][j] <= 100
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Simulating with a direction array and a visited matrix works but needs O(m * n) extra space. A cleaner way is to peel the matrix layer by layer using four boundaries. Walk the top row, then move top down; walk the right column, then move right left; and so on. The only trap is a single remaining row or column, which the two extra boundary checks handle.
Algorithm
- Set
top = 0,bottom = m - 1,left = 0,right = n - 1. - While
top <= bottomandleft <= right: walk the top row left to right, thentop++. - Walk the right column top to bottom, then
right--. - If
top <= bottom, walk the bottom row right to left, thenbottom--. - If
left <= right, walk the left column bottom to top, thenleft++.
O(m * n)Space: O(1) extra (besides the output)[[1,2,3]] and a single column like [[1],[2],[3]]. Missing boundary checks show up as repeated values in exactly these cases.class Solution: def spiralOrder(self, matrix: List[List[int]]) -> List[int]: ans = [] top, bottom, left, right = 0, len(matrix) - 1, 0, len(matrix[0]) - 1 while top <= bottom and left <= right: for j in range(left, right + 1): ans.append(matrix[top][j]) top += 1 for i in range(top, bottom + 1): ans.append(matrix[i][right]) right -= 1 if top <= bottom: # a bottom row is still left for j in range(right, left - 1, -1): ans.append(matrix[bottom][j]) bottom -= 1 if left <= right: # a left column is still left for i in range(bottom, top - 1, -1): ans.append(matrix[i][left]) left += 1 return ans