-
Notifications
You must be signed in to change notification settings - Fork 0
167 — Spiral Matrix
LeetCode 54 · Medium. Given an m x n matrix, return all its elements in spiral order — starting at the top-left corner, walking right across the top row, down the right column, left across the bottom row, up the left column, then spiraling inward and repeating until every cell has been visited.
Picture mowing a rectangular lawn in a shrinking spiral: you walk the full top edge left to right, turn and walk the full right edge top to bottom, turn and walk the bottom edge right to left, turn and walk the left edge bottom to top — and now the outermost ring is done, so you tighten the boundary inward on all four sides and repeat the same four-turn loop on the smaller rectangle that's left. You never need to "remember" where you've already mowed, because each pass's boundaries are simply narrower than the last.
matrix: walk order, one edge at a time:
1 2 3 4
5 6 7 8 top edge (row 0, left->right): 1, 2, 3, 4
9 10 11 12 right edge (col 3, top->bottom,
below the corner already taken): 8, 12
bottom edge (row 2, right->left,
left of the corner already taken): 11, 10, 9
left edge (col 0, bottom->top,
between the corners already taken): 5
full spiral order: 1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7
"Return elements in spiral order" on a 2-D grid is the boundary-shrinking traversal signal: instead of asking "where do I go from here?" cell by cell forever, track four edges — top, bottom, left, right — walk each edge fully in the right direction, then shrink the edge you just finished inward. The moment the shrinking boundaries cross, every cell has been visited exactly once.
Simulate the walk literally: keep a visited grid, walk in the current direction until the next step would leave the grid or land on an already-visited cell, and only then turn 90 degrees clockwise.
func spiralOrderBruteForce(_ matrix: [[Int]]) -> [Int] {
guard !matrix.isEmpty, !matrix[0].isEmpty else { return [] }
let rows = matrix.count
let cols = matrix[0].count
var visited = Array(repeating: Array(repeating: false, count: cols), count: rows)
var result: [Int] = []
let directions = [(0, 1), (1, 0), (0, -1), (-1, 0)] // right, down, left, up
var dirIndex = 0
var r = 0, c = 0
for _ in 0..<(rows * cols) {
result.append(matrix[r][c])
visited[r][c] = true
var nr = r + directions[dirIndex].0
var nc = c + directions[dirIndex].1
if nr < 0 || nr >= rows || nc < 0 || nc >= cols || visited[nr][nc] {
dirIndex = (dirIndex + 1) % 4
nr = r + directions[dirIndex].0
nc = c + directions[dirIndex].1
}
r = nr
c = nc
}
return result
}
// smoke test
print(spiralOrderBruteForce([[1,2,3],[4,5,6],[7,8,9]]))
// [1, 2, 3, 6, 9, 8, 7, 4, 5]
print(spiralOrderBruteForce([[1,2,3,4],[5,6,7,8],[9,10,11,12]]))
// [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]Big-O: O(m * n) time — each cell is visited once. O(m * n) extra space for the visited grid.
Track four shrinking boundaries instead of a visited grid: walk the top row left-to-right, the right column top-to-bottom, the bottom row right-to-left, the left column bottom-to-top — shrinking the relevant boundary after each edge, and stopping the moment the boundaries cross.
func spiralOrder(_ matrix: [[Int]]) -> [Int] {
guard !matrix.isEmpty, !matrix[0].isEmpty else { return [] }
var result: [Int] = []
var top = 0, bottom = matrix.count - 1
var left = 0, right = matrix[0].count - 1
while top <= bottom && left <= right {
for c in left...right {
result.append(matrix[top][c])
}
top += 1
if top > bottom { break }
for r in top...bottom {
result.append(matrix[r][right])
}
right -= 1
if left > right { break }
for c in stride(from: right, through: left, by: -1) {
result.append(matrix[bottom][c])
}
bottom -= 1
if top > bottom { break }
for r in stride(from: bottom, through: top, by: -1) {
result.append(matrix[r][left])
}
left += 1
}
return result
}
// smoke test — same cases as the brute force
print(spiralOrder([[1,2,3],[4,5,6],[7,8,9]]))
// [1, 2, 3, 6, 9, 8, 7, 4, 5]
print(spiralOrder([[1,2,3,4],[5,6,7,8],[9,10,11,12]]))
// [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]Big-O: O(m * n) time — each cell is still visited exactly once, but with less per-cell bookkeeping. O(1) extra space beyond the output array — no visited grid needed.
The brute force needs a visited grid because it doesn't structurally know when a direction has run out — it has to ask the grid, cell by cell, "have I been here, or is this off the edge?" But a spiral's structure is completely predictable: once you finish the top row, that row can never be revisited, so the boundary can simply move down and never be checked again. Four shrinking boundaries encode exactly the same information a visited grid would answer cell-by-cell, except they update in four bulk moves instead of m * n individual lookups — trading a whole auxiliary grid for four integers.
- Arrays and Strings — the 2-D array being walked; each edge traversal is a plain 1-D scan across a row or column slice.
- Matrix Traversal — the bounded, shrinking-perimeter walk over a 2-D grid, here structured by boundary variables rather than by DFS/BFS over neighbors.
Spiral Matrix is mowing a lawn in shrinking rectangles — walk each of the four edges fully, tighten the boundary after every edge, and stop the moment the shrinking rectangle disappears.
- Why does the optimal solution need an
if top > bottom { break }check after the first edge but not need an equivalent check before it? - Walk through what happens on a single-row matrix like
[[1, 2, 3, 4]]. Which of the fourforloops actually execute, and why don't the "down the right column" and "up the left column" loops double-count any elements? - The brute force turns 90 degrees only when the next step would be invalid. Why is this reactive check necessary there, but not needed at all in the boundary-shrinking version?
- Why is
O(m * n)the best possible time complexity for this problem regardless of approach, even though the optimal solution avoids the brute force's extra space?