MediumBlind75MatrixSimulation
Spiral Matrix
Given an m x n matrix, return all elements of the matrix in spiral order.
Examples
Input
matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output
[1,2,3,6,9,8,7,4,5]
Spiral order: right, down, left, up, right.
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]
Spiral order traversal.
Constraints
- •
m == matrix.length - •
n == matrix[i].length - •
1 <= m, n <= 10 - •
-100 <= matrix[i][j] <= 100
Approaches
Simulate the spiral movement, marking visited cells.
CodeT: O(m * n) | S: O(m * n)
def spiral_order(matrix):
if not matrix:
return []
result = []
visited = [[False] * len(matrix[0]) for _ in range(len(matrix))]
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
dir_idx = 0
row, col = 0, 0
for _ in range(len(matrix) * len(matrix[0])):
result.append(matrix[row][col])
visited[row][col] = True
next_row = row + directions[dir_idx][0]
next_col = col + directions[dir_idx][1]
if (next_row < 0 or next_row >= len(matrix) or
next_col < 0 or next_col >= len(matrix[0]) or
visited[next_row][next_col]):
dir_idx = (dir_idx + 1) % 4
row += directions[dir_idx][0]
col += directions[dir_idx][1]
return resultProcess the matrix layer by layer, spiraling inward.
CodeT: O(m * n) | S: O(1)
def spiral_order(matrix):
result = []
if not matrix:
return result
top, bottom = 0, len(matrix) - 1
left, right = 0, len(matrix[0]) - 1
while top <= bottom and left <= right:
for i in range(left, right + 1):
result.append(matrix[top][i])
top += 1
for i in range(top, bottom + 1):
result.append(matrix[i][right])
right -= 1
if top <= bottom:
for i in range(right, left - 1, -1):
result.append(matrix[bottom][i])
bottom -= 1
if left <= right:
for i in range(bottom, top - 1, -1):
result.append(matrix[i][left])
left += 1
return resultSame layer approach with cleaner boundary checks.
Diagram
matrix = [[1,2,3],[4,5,6],[7,8,9]]
Pop top: [1,2,3]
Pop right col: [6,9]
Pop bottom: [8,7]
Pop left col: [4,5]
Result: [1,2,3,6,9,8,7,4,5]
CodeT: O(m * n) | S: O(1)
def spiral_order(matrix):
result = []
while matrix:
result += matrix.pop(0)
if matrix and matrix[0]:
for row in matrix:
result.append(row.pop())
if matrix:
result += matrix.pop()[::-1]
if matrix and matrix[0]:
for row in matrix[::-1]:
result.append(row.pop(0))
return resultComplexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Simulation - Mark Visited | O(m * n) | O(m * n) | Simulate the spiral movement, marking visited cells. |
| Layer by Layer | O(m * n) | O(1) | Process the matrix layer by layer, spiraling inward. |
| Optimized Layer Processing | O(m * n) | O(1) | Same layer approach with cleaner boundary checks. |
Simulation - Mark Visited
T: O(m * n)S: O(m * n)
Simulate the spiral movement, marking visited cells.
Layer by Layer
T: O(m * n)S: O(1)
Process the matrix layer by layer, spiraling inward.
Optimized Layer Processing
T: O(m * n)S: O(1)
Same layer approach with cleaner boundary checks.
Common Mistakes
Not handling the case where the matrix is not square
Forgetting to check boundaries after each direction change
Using extra space when O(1) is possible