0054 Spiral Matrix#
Problem#
Given an m x n
matrix, return all elements of the matrix in spiral order
.
Examples#
Example 1:
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]
Example 2:
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#
m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrix[i][j] <= 100
Analysis#
define 4 boundaries
traverse along the boundary clockwise until reach out of bounds
shrink the bounds
Solution#
def spiralOrder(matrix):
m, n = len(matrix), len(matrix[0])
l, r, u, d = 0, n-1, 0, m-1
res = []
while u <= d and l <= r:
# move along upper boud from left to right
for i in range(l, r+1):
res.append(matrix[u][i])
u += 1
# move along right bound from up to down
for j in range(u, d+1):
res.append(matrix[j][r])
r -= 1
# move along lower bound from right to left
if u <= d: # avoid traverse again
for i in range(r, l-1, -1):
res.append(matrix[d][i])
d -= 1
# move along left bound from down to up
if l <= r:
for j in range(d, u-1, -1):
res.append(matrix[j][l])
l += 1
return res
# test
matrix = [[1,2,3],[4,5,6],[7,8,9]]
print(spiralOrder(matrix))
matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
print(spiralOrder(matrix))
matrix = [[1,2,3,4,5]]
print(spiralOrder(matrix))
matrix = [[1], [2], [3], [4], [5]]
print(spiralOrder(matrix))
[1, 2, 3, 6, 9, 8, 7, 4, 5]
[1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]
[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5]