← DSA Atlas
Dedicated problem page · #885

Spiral Matrix III

MediumMatrix and SimulationExpanding clockwise spiral with growing leg lengthsDirection cycling + arithmetic step sequence 1,1,2,2,3,3,...
Solve on LeetCode ↗
885
MediumMatrix and SimulationDirection cycling + arithmetic step sequence 1,1,2,2,3,3,...Expanding clockwise spiral with growing leg lengths

Spiral Matrix III

You start at cell (rStart, cStart) in a rows x cols grid, facing east, and walk in a clockwise spiral. You keep spiraling outward, and whenever your path leaves the grid you still walk those steps but skip recording out-of-bounds cells. Return the coordinates of all rows*cols grid cells in the order you first visit them.

Open official problem prompt ↗
In plain English

Emit every grid cell in the order an outward clockwise spiral starting at an arbitrary cell would first touch it, ignoring steps that land outside the grid.

Picture it like this

Like a lighthouse beam sweeping in ever-widening square loops from where you stand: you keep circling outward, and you only note the buildings that are actually inside the city limits.

Example
Input
rows = 1, cols = 4, rStart = 0, cStart = 0
Output
[[0,0],[0,1],[0,2],[0,3]]
Why
From (0,0) the outward spiral first records the two in-bounds cells to the east, and after looping around it eventually records (0,2) and (0,3), covering all 4 cells of the single row.
Constraints
1 <= rows, cols <= 1000 <= rStart < rows0 <= cStart < cols
Pattern lesson

See the pattern, then code

Expanding clockwise spiral with growing leg lengths
Recognition clue

You must generate a spiral from an arbitrary interior start and the spiral may run outside the grid; the fixed leg-length growth pattern of a spiral (1,1,2,2,3,3,...) is the signal.

↗
Matrix and Simulation

Rotations, boundary walks, direction changes, or careful in-place state updates.. A clockwise spiral moves East, South, West, North repeatedly, and the number of steps per leg follows 1,1,2,2,3,3,... increasing by one every two legs. Walk that pattern from the start; record only cells that fall inside the grid and stop once you have collected all rows*cols of them.

New words, made simpleKnow these before the algorithm
Spiral leg
A straight run in one direction before the next clockwise turn.
Leg-length pattern
The counts 1,1,2,2,3,3,... of steps per leg, growing by one every two turns.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Bounded spiral shrinking borders

Does not fit here: the start is arbitrary and the spiral must legally step outside the grid.

The classic four-border spiral used when you start at a corner and never leave the grid.

Time O(rows*cols)Space O(rows*cols)
Best choiceDirection cycling with growing legs

Handles arbitrary start and out-of-bounds legs cleanly; the intended approach.

Follow the 1,1,2,2,3,3 leg pattern outward, recording only in-bounds cells until all are found.

Time O(max(rows,cols)^2)Space O(rows*cols)
The rule we keep true

Invariant

At the start of each leg, (r, c) is the last position on the spiral path, res contains exactly the in-bounds cells visited so far in spiral order, and step equals the length of the current leg per the 1,1,2,2,... pattern.

Why this is correct

Reasoning

The spiral geometrically expands to cover an ever-larger square region around the start, so it is guaranteed to eventually pass through every grid cell; recording only in-bounds cells and stopping at rows*cols collected cells yields exactly the grid in first-visit order.

The algorithm in three movesSay these aloud before coding
1Record the start cell and set direction to East with step length 0

leg E len1 -> record (0,1)

2Increase the leg length by 1 whenever the direction is East or West (i.e. every two turns)

leg S/W/N mostly out of bounds

3Take that many unit steps in the current direction, appending only in-bounds cells

later legs record (0,2) then (0,3); count=4 stop

4Rotate clockwise to the next direction and repeat until all rows*cols cells are recorded

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
(0,0)0
(0,1)1
(0,2)2
(0,3)3
1 · Read(0,0)
2 · Askseed result
3 · Update stateres=[[0,0]], step=0, d=0(E)
4 · Result1 of 4 recorded
Key takeaway

The four cells of the 1x4 grid in visitation order; the walk starts at the highlighted (0,0).

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3Clockwise direction order

    East, South, West, North so cycling d with (d+1)%4 turns right each leg.

  2. 2
    Lines 8-9Grow the leg every two turns

    Incrementing step only when d is even (East or West) reproduces the 1,1,2,2,3,3 pattern.

  3. 3
    Lines 10-15Walk the leg, record in-bounds only

    Move one cell at a time; append to result only when the cell is inside the grid, so out-of-bounds detours are silently skipped.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Start at a corner: behaves like a normal spiral but still tolerates outside steps
  • 1x1 grid: the seeded start alone already satisfies rows*cols=1
  • Single row or single column: most legs are out of bounds and get skipped
  • Start in the exact center of a square grid
!

Common beginner mistakes

  • Increasing the leg length every turn instead of every two turns, breaking the 1,1,2,2 pattern
  • Stopping the walk at grid borders instead of continuing the spiral outside them
  • Recording out-of-bounds cells, or using a shrinking-border spiral that cannot start mid-grid
  • Off-by-one on the termination check: loop until len(res) == rows*cols, not a fixed number of legs
Check your understanding

Why does the leg length increase only on every second turn rather than every turn?

More in Matrix and Simulation

#6Zigzag ConversionRow-index simulation with bouncing direction#48Rotate ImageTranspose then reverse rows#54Spiral MatrixShrinking boundary walk#59Spiral Matrix IIShrinking boundary fill#73Set Matrix ZeroesFirst row/column as marker storage#289Game of LifeIn-place bit-encoded next state