[LeetCode] 054. Spiral Matrix
-
date_range April 08, 2019 - Monday info
Problem (Medium)
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
Example 1:
Input:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]
Example 2:
Input:
[
[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]
Approach 1: (My Solution)
Idea
Straight forward idea:
- loop and switch direction when hit boundary,
- pop the ‘already-looped’ row or column.
Solution
class Solution1:
def spiralOrder(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
i, j, res = 0, 0, []
mode = 0
while len(matrix) and len(matrix[0]):
res.append(matrix[i][j])
if mode == 0:
if j == len(matrix[0])-1:
matrix.pop(0)
mode = (mode+1) % 4
else:
j += 1
elif mode == 1:
if i == len(matrix)-1:
for k in range(len(matrix)):
matrix[k].pop(-1)
j -= 1
mode = (mode+1) % 4
else:
i += 1
elif mode == 2:
if j == 0:
matrix.pop(-1)
mode = (mode+1) % 4
i -= 1
else:
j -= 1
elif mode == 3:
if i == 0:
for k in range(len(matrix)):
matrix[k].pop(0)
mode = (mode+1) % 4
else:
i -= 1
#print('mode:', mode, 'i:', i, 'j:', j)
#print('matrix:', matrix)
return res
Complexity
- Time: $O(N)$ where $N$ is the total number of elements in the input matrix.
- Space: $O(N)$
KF