Spiral Matrix
Problem Statement
Given an m x n
matrix of integers matrix
, return a list of all elements within the matrix in spiral order.
Example 1:
# Input: matrix = [[1,2],[3,4]]# Output: [1,2,4,3]
Example 2:
# Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]# Output: [1,2,3,6,9,8,7,4,5]
Example 3:
# 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 <= matrix.length, matrix[i].length <= 10
-100 <= matrix[i][j] <= 100
Recommended Time and Space Complexity
You should aim for a solution with O(m * n)
time and O(1)
space, where m
is the number of rows and n
is the number of columns.
Hint 1
Think about how the spiral traversal can be broken down into layers.
Hint 2
Consider using pointers to keep track of the boundaries of the current layer.
Hint 3
Be mindful of edge cases, such as when the matrix has only one row or one column.
Solution
Recursion
def spiral_order(matrix: List[List[int]]) -> List[int]: m, n = len(matrix), len(matrix[0]) res = []
def dfs(row, col, r, c, dr, dc): if row == 0 or col == 0: return
for i in range(col): r += dr c += dc res.append(matrix[r][c])
dfs(col, row - 1, r, c, dc, -dr)
dfs(m, n, 0, -1, 0, 1) return res
Time complexity: O(m * n)
Space complexity: O(min(m, n))