Given an m x n matrix, return all elements of the matrix in spiral order. (Starts with the right direction and goes clockwise).
Example 1: Input:
matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output:[1,2,3,6,9,8,7,4,5]—
This problem is pretty straightforward. We simply have to traverse the 2d matrix in a spiral direction. We can save memory by marking directly on the matrix. Since the possible values are from -100 to 100, I used 999 to mark it (anything that doesn’t overlap with the given input values can be used).
Since we know the matrix size and we know each cell is visited only once, we can loop through every element of the array, m x n.
We also rotate the direction it’s traveling in every time we hit the boundary or a visited cell. Then as we traverse, we’ll save the results on a separate array.
Here’s the implementation:
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
res = []
m, n = len(matrix), len(matrix[0])
i, j, x, y = 0, 0, 1, 0
for _ in range(m * n):
res.append(matrix[i][j])
matrix[i][j] = 999
if i + y >= m or j + x >= n or matrix[i + y][j + x] == 999:
x, y = -y, x # rotate cw
i += y
j += x
return res
Time: O(nm)
Space: O(nm)