NeetCode #904LC-885MediumMath & Geometry
← Back to All Problems#904 · #885 · Spiral Matrix III(螺旋矩阵 III)
📌 Problem Statement & Constraints
Starting at
(rStart, cStart) in a rows x cols grid, walk clockwise in a spiral: east, south, west, north, then east again, expanding the radius each time a full cycle is completed. Return the coordinates of all rows * cols cells in the order they are first visited, skipping any cell outside the grid. Constraints: 1 <= rows, cols <= 100, 0 <= rStart < rows, 0 <= cStart < cols.💡 Core Algorithmic Approaches
- The walk follows a fixed direction cycle: east, south, west, north.
- The number of steps per direction increases by one after every two directions: 1, 1, 2, 2, 3, 3, and so on.
- Simulate the walk, recording a cell only when it lies inside the grid, and stop once
rows * colscells have been collected. - Because the spiral expands without bound, termination is driven by the collected count, not by the radius.
💻 Benchmark Python3 Implementation
class Solution:
def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:
res = [[rStart, cStart]]
total = rows * cols
dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)] # east, south, west, north
r, c, d = rStart, cStart, 0
step = 1
while len(res) < total:
for _ in range(2): # two directions per step length
dr, dc = dirs[d % 4]
for _ in range(step):
r += dr
c += dc
if 0 <= r < rows and 0 <= c < cols:
res.append([r, c])
if len(res) == total:
return res
d += 1
step += 1
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(max(rows, cols)^2): the spiral grows until it has covered the whole grid.
💾 Space Complexity
O(rows * cols): the output list.
⚠️ Interview Pitfalls & Follow-ups
- Increasing the step length after every direction: it increases after every two directions, producing the 1, 1, 2, 2, 3, 3 pattern.
- Recording out-of-bounds cells: only in-grid cells are appended, but the walk must still traverse the out-of-bounds positions.
- Stopping after a fixed number of steps: termination is determined by the collected cell count.
- Failing to advance the direction index:
dmust increment after each side so thatd % 4cycles correctly.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.