Spiral Matrix III
Medium · Matrix · Array · Matrix · Simulation
Problem
You stand on cell (rStart, cStart) of a rows x cols grid, facing east. Walk outward in a clockwise spiral: 1 step east, 1 south, 2 west, 2 north, 3 east, 3 south, and so on, each pair of legs one step longer than the pair before.
Part of the spiral leaves the grid; keep walking outside it anyway, because the path re-enters later. Record each cell inside the grid the first time you stand on it, starting with the start cell.
Return the list of [row, col] coordinates in the order you visited them, stopping once all rows * cols cells have been recorded. Row numbers grow going south and column numbers going east.
Examples
Input: rows = 1, cols = 3, rStart = 0, cStart = 0 Output: [[0,0],[0,1],[0,2]]
From (0,0) you step east to (0,1). The next legs (south, west, north, then east along row -1) stay outside the grid, and the south leg after them passes (0,2).
Input: rows = 2, cols = 3, rStart = 1, cStart = 1 Output: [[1,1],[1,2],[1,0],[0,0],[0,1],[0,2]]
East reaches (1,2). The south step leaves the grid; coming back west, the walk crosses row 2 (outside) and the north leg enters (1,0) and (0,0). The next east leg collects the rest of the top row.
Constraints
- 1 <= rows, cols <= 100
- 0 <= rStart < rows
- 0 <= cStart < cols
Approaches
- Baseline: walk every step — time O(max(rows, cols)²), space O(1) beyond the output
Follow-up
On a grid with no edges, the same leg structure answers two more questions without walking every step: where you are after k steps (skip whole legs, O(√k)), and after how many steps you first reach a given cell. Those are the use cases.
Related problems
Start free on Cariara · Coding problems · System design studio
