# LeetCode 885: Spiral Matrix III

## Problem Restatement

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

We start at cell:

```text
(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

| Item | Meaning |
|---|---|
| Input | `rows`, `cols`, `rStart`, `cStart` |
| Output | List of coordinates visited inside the grid |
| Start | `(rStart, cStart)` |
| Initial direction | East |
| Movement shape | Clockwise spiral |
| Outside grid | Keep walking, but do not record invalid cells |

Function shape:

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

## Examples

Example 1:

```text
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:

```text
(0,0), (0,1), (0,2), (0,3)
```

Example 2:

```text
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:

```text
1, 1, 2, 2, 3, 3, 4, 4, ...
```

The directions repeat in this order:

| Direction | Row change | Column change |
|---|---:|---:|
| East | 0 | 1 |
| South | 1 | 0 |
| West | 0 | -1 |
| North | -1 | 0 |

So the walk is:

```text
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:

```text
rows * cols
```

coordinates.

## Algorithm

Start with the initial coordinate in the answer.

Use a direction array:

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

Initialize:

```python
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:

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

Start:

```text
answer = [[0,0]]
```

Move east `1`:

```text
(0,1)
```

inside grid, record it.

Move south `1`:

```text
(1,1)
```

outside grid, do not record.

Move west `2`:

```text
(1,0), (1,-1)
```

both outside grid.

Move north `2`:

```text
(0,-1), (-1,-1)
```

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

Move east `3`:

```text
(-1,0), (-1,1), (-1,2)
```

outside grid.

Move south `3`:

```text
(0,2), (1,2), (2,2)
```

record `(0,2)`.

The process continues until all four cells are recorded:

```text
[[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:

```python
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:

```text
R = rows
C = cols
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(max(R, C)^2)` | The spiral may walk outside the grid before collecting all cells |
| Space | `O(R * C)` | The output stores every grid coordinate |

The output itself contains `R * C` coordinates.

## Implementation

```python
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:

```python
result = [[rStart, cStart]]
```

The direction array stores one clockwise cycle:

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

The current position is tracked by:

```python
row = rStart
col = cStart
```

The spiral starts with step length `1`:

```python
step_length = 1
```

Each step length is used for two directions:

```python
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:

```python
row += dr
col += dc
```

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

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

After finishing a direction, we turn clockwise:

```python
direction_index = (direction_index + 1) % 4
```

After two directions, the spiral expands:

```python
step_length += 1
```

The loop stops once every grid cell has been recorded.

## Testing

```python
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:

| Test | Why |
|---|---|
| `1 x 4`, start at left edge | Official small row example |
| `1 x 1` | Minimum grid |
| `2 x 2`, corner start | Spiral stays mostly inside |
| `3 x 3`, center start | Clean centered spiral |
| `5 x 6`, off-center start | Checks size, uniqueness, and boundaries |