⚡Flashcard Drill➔
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

  1. The walk follows a fixed direction cycle: east, south, west, north.
  2. The number of steps per direction increases by one after every two directions: 1, 1, 2, 2, 3, 3, and so on.
  3. Simulate the walk, recording a cell only when it lies inside the grid, and stop once rows * cols cells have been collected.
  4. 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: d must increment after each side so that d % 4 cycles correctly.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Math & Geometry Problems