Date and Time: Jul 14, 2024, 12:55 (EST)
Link: https://leetcode.com/problems/spiral-matrix/
| Access Time | Time | Y/N |
|---|---|---|
| Jun 15, 2025 | Y |
We just repeat four directions moving: left -> right, top -> bottom, right -> left, bottom -> top with four pointers l, r, t, b to indicate these four boundaries.
We need to be careful, after we finish the first two operations from l->r, t->b, we increment t += 1 and decrement r -= 1. In this time, we want to check if t <= b, so we can operate r->l, since l->r and r->l can't operate on the same row to avoid duplicate, if t = b + 1 will have duplicate (cuz we just increment t += 1, it means t == b before l->r operation). Same thing to check if l <= r, to avoid adding duplicate on the same row.
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
# l, r, t, b to indicate four boundaries
# Repeat l->r, t->b, r->l, b->t until l == r or t == b
# TC: O(m*n), SC: O(1)
rows, cols = len(matrix), len(matrix[0])
l, r, t, b = 0, cols-1, 0, rows-1
ans = []
while l <= r and t <= b:
# l->r, move t downward
for i in range(l, r+1):
ans.append(matrix[t][i])
t += 1
# t->b, move r to the left
for i in range(t, b+1):
ans.append(matrix[i][r])
r -= 1
# Processing opposite directions from l->r and t->b
# They are only valid to go when t <= b and l <= r
# Otherwise, don't run if they are out of bound
# r->l, move b upward
if t <= b:
for i in range(r, l-1, -1):
ans.append(matrix[b][i])
b -= 1
# b->t, move l to the right
if l <= r:
for i in range(b, t-1, -1):
ans.append(matrix[i][l])
l += 1
return ansTime Complexity:
Space Complexity:
