# Spiral Matrix

Array

## # Solution

Let $N$ be the number of total elements in the matrix.

### # Simulation

Need seen and bounds checking to decide if next move needs to change direction.

Complexity

time: $O(N)$
space: $O(N)$

def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
res = []
if not matrix: return res
R, C = len(matrix), len(matrix[0])
seen = [[False for _ in range(C)] for _ in range(R)]
r = c = di = 0
dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]

for _ in range(R * C):
res.append(matrix[r][c])
seen[r][c] = True
nr, nc = r+dr[di], c+dc[di]
if 0 <= nr < R and 0 <= nc < C and not seen[nr][nc]:
r, c = nr, nc
else:
di = (di + 1) % 4
r, c = r+dr[di], c+dc[di]
return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

### # Loop Inward

def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
res = []
if not matrix: return res
R, C = len(matrix), len(matrix[0])
r1 = 0
r2 = R - 1
c1 = 0
c2 = C - 1
while r1 <= r2 and c1 <= c2:
# top: c from c1 ... c2
for c in range(c1, c2+1):
res.append(matrix[r1][c])
# right: r from r1+1 ... r2
for r in range(r1+1, r2+1):
res.append(matrix[r][c2])
if r1<r2 and c1<c2:
# bottom: c from c2-1 ... c1+1
for c in range(c2-1, c1, -1):
res.append(matrix[r2][c])
# left: r from r2 ... r1+1
for r in range(r2, r1, -1):
res.append(matrix[r][c1])
r1 += 1
c1 += 1
r2 -= 1
c2 -= 1
return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27