LeetCode 885: Spiral Matrix III

Problem Restatement

We are given a grid with rows rows and cols columns.

We start at cell:

(rStart, cStart)

Initially, we face east.

We walk in a clockwise spiral until every grid cell has been visited. The walk may go outside the grid boundary, but we only record coordinates that are inside the grid.

Return the grid coordinates in the order we visit them.

LeetCode defines the northwest corner as (0, 0) and the southeast corner as (rows - 1, cols - 1). The path continues even outside the grid, and eventually reaches every grid cell.

Input and Output

Function shape:

def spiralMatrixIII(
    self,
    rows: int,
    cols: int,
    rStart: int,
    cStart: int
) -> list[list[int]]:
    ...

Examples

Example 1:

Input: rows = 1, cols = 4, rStart = 0, cStart = 0
Output: [[0,0],[0,1],[0,2],[0,3]]

The grid has one row.

Starting at (0, 0), the spiral first moves east, so it visits:

(0,0), (0,1), (0,2), (0,3)

Example 2:

Input: rows = 5, cols = 6, rStart = 1, cStart = 4
Output:
[
  [1,4],[1,5],[2,5],[2,4],[2,3],
  [1,3],[0,3],[0,4],[0,5],[3,5],
  [3,4],[3,3],[3,2],[2,2],[1,2],
  [0,2],[4,5],[4,4],[4,3],[4,2],
  [4,1],[3,1],[2,1],[1,1],[0,1],
  [4,0],[3,0],[2,0],[1,0],[0,0]
]

The path walks in a spiral around (1, 4) and records only cells inside the 5 x 6 grid.

First Thought: Mark Cells While Turning at Boundaries

For normal spiral matrix problems, we often turn when we hit a boundary or a visited cell.

That does not work here.

The path is allowed to leave the grid. We still keep walking outside the grid and may return later.

So the turning rule cannot depend on grid boundaries. It must depend only on the spiral step pattern.

Key Insight

The movement lengths follow a simple pattern:

1, 1, 2, 2, 3, 3, 4, 4, ...

The directions repeat in this order:

So the walk is:

east 1
south 1
west 2
north 2
east 3
south 3
west 4
north 4
...

After every two directions, the step length increases by 1.

Whenever the current coordinate is inside the grid, append it to the answer.

Stop when the answer contains:

rows * cols

coordinates.

Algorithm

Start with the initial coordinate in the answer.

Use a direction array:

directions = [
    (0, 1),   # east
    (1, 0),   # south
    (0, -1),  # west
    (-1, 0),  # north
]

Initialize:

step_length = 1
direction_index = 0

While we have not recorded all cells:

1. Move step_length steps in the current direction.
2. Record every position inside the grid.
3. Turn clockwise.
4. After every two turns, increase step_length.

Walkthrough

Use:

rows = 1
cols = 4
rStart = 0
cStart = 0

Start:

answer = [[0,0]]

Move east 1:

(0,1)

inside grid, record it.

Move south 1:

(1,1)

outside grid, do not record.

Move west 2:

(1,0), (1,-1)

both outside grid.

Move north 2:

(0,-1), (-1,-1)

(0,-1) is outside. (-1,-1) is outside.

Move east 3:

(-1,0), (-1,1), (-1,2)

outside grid.

Move south 3:

(0,2), (1,2), (2,2)

record (0,2).

The process continues until all four cells are recorded:

[[0,0],[0,1],[0,2],[0,3]]

Correctness

The algorithm follows the exact spiral movement rule.

The directions are east, south, west, and north, then repeat. This matches a clockwise spiral starting while facing east.

The step lengths are 1, 1, 2, 2, 3, 3, .... This is the required expanding spiral pattern. Each pair of directions uses the same length, then the length increases by one, causing the path to expand outward.

The algorithm records a coordinate only when it satisfies:

0 <= row < rows and 0 <= col < cols

Therefore, every recorded coordinate is a valid grid cell.

The spiral keeps expanding without limit, so it eventually covers a rectangle large enough to include the whole grid. Since the algorithm stops only after recording rows * cols valid cells, it records every grid cell.

The spiral path never visits the same coordinate twice. Therefore, no grid cell is recorded twice.

Thus, the returned list contains every grid coordinate exactly once, in the order visited by the spiral walk.

Complexity

Let:

R = rows
C = cols

The output itself contains R * C coordinates.

Implementation

class Solution:
    def spiralMatrixIII(
        self,
        rows: int,
        cols: int,
        rStart: int,
        cStart: int
    ) -> list[list[int]]:
        result = [[rStart, cStart]]

        directions = [
            (0, 1),
            (1, 0),
            (0, -1),
            (-1, 0),
        ]

        row = rStart
        col = cStart
        step_length = 1
        direction_index = 0

        while len(result) < rows * cols:
            for _ in range(2):
                dr, dc = directions[direction_index]

                for _ in range(step_length):
                    row += dr
                    col += dc

                    if 0 <= row < rows and 0 <= col < cols:
                        result.append([row, col])

                        if len(result) == rows * cols:
                            return result

                direction_index = (direction_index + 1) % 4

            step_length += 1

        return result

Code Explanation

We start by recording the starting cell:

result = [[rStart, cStart]]

The direction array stores one clockwise cycle:

directions = [
    (0, 1),
    (1, 0),
    (0, -1),
    (-1, 0),
]

The current position is tracked by:

row = rStart
col = cStart

The spiral starts with step length 1:

step_length = 1

Each step length is used for two directions:

for _ in range(2):

For example, length 1 is used for east and south. Length 2 is used for west and north.

Inside each direction, we move one cell at a time:

row += dr
col += dc

If the coordinate is inside the grid, we record it:

if 0 <= row < rows and 0 <= col < cols:
    result.append([row, col])

After finishing a direction, we turn clockwise:

direction_index = (direction_index + 1) % 4

After two directions, the spiral expands:

step_length += 1

The loop stops once every grid cell has been recorded.

Testing

def run_tests():
    s = Solution()

    assert s.spiralMatrixIII(1, 4, 0, 0) == [
        [0, 0], [0, 1], [0, 2], [0, 3]
    ]

    assert s.spiralMatrixIII(1, 1, 0, 0) == [
        [0, 0]
    ]

    assert s.spiralMatrixIII(2, 2, 0, 0) == [
        [0, 0], [0, 1], [1, 1], [1, 0]
    ]

    assert s.spiralMatrixIII(3, 3, 1, 1) == [
        [1, 1], [1, 2], [2, 2], [2, 1], [2, 0],
        [1, 0], [0, 0], [0, 1], [0, 2]
    ]

    ans = s.spiralMatrixIII(5, 6, 1, 4)
    assert len(ans) == 30
    assert len({tuple(cell) for cell in ans}) == 30
    assert all(0 <= r < 5 and 0 <= c < 6 for r, c in ans)

    print("all tests passed")

run_tests()

Test meaning: