# LeetCode 54: Spiral Matrix

## Problem Restatement

We are given an `m x n` matrix.

We need to return all elements of the matrix in spiral order.

The spiral starts at the top-left cell. It moves:

1. Right across the top row
2. Down the right column
3. Left across the bottom row
4. Up the left column

Then it repeats the same pattern on the inner part of the matrix.

The official constraints are `1 <= m, n <= 10` and `-100 <= matrix[i][j] <= 100`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A 2D integer matrix |
| Output | A list of integers in spiral order |
| Matrix size | `m x n` |
| Traversal | Visit each cell exactly once |

Function shape:

```python
def spiralOrder(matrix: list[list[int]]) -> list[int]:
    ...
```

## Examples

For:

```python
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
]
```

The spiral order is:

```python
[1, 2, 3, 6, 9, 8, 7, 4, 5]
```

We first read the top row:

```text
1, 2, 3
```

Then the right column:

```text
6, 9
```

Then the bottom row from right to left:

```text
8, 7
```

Then the left column from bottom to top:

```text
4
```

Finally, the center:

```text
5
```

For:

```python
matrix = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12],
]
```

The answer is:

```python
[1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]
```

## First Thought: Simulate Movement

One way is to simulate the actual movement.

Start at `(0, 0)`.

Move right until the next cell is outside the matrix or already visited. Then turn down. Then turn left. Then turn up. Repeat until all cells have been visited.

This works, but it needs a `visited` matrix or it needs to modify the input matrix.

There is a cleaner approach.

## Key Insight

A spiral traversal reads the matrix layer by layer.

Each layer has four boundaries:

| Boundary | Meaning |
|---|---|
| `top` | First unvisited row |
| `bottom` | Last unvisited row |
| `left` | First unvisited column |
| `right` | Last unvisited column |

For each layer:

1. Read the top row from left to right.
2. Move `top` down.
3. Read the right column from top to bottom.
4. Move `right` left.
5. Read the bottom row from right to left, if it still exists.
6. Move `bottom` up.
7. Read the left column from bottom to top, if it still exists.
8. Move `left` right.

The checks before reading the bottom row and left column matter because rectangular matrices can collapse into a single row or a single column.

## Algorithm

Initialize:

```python
top = 0
bottom = len(matrix) - 1
left = 0
right = len(matrix[0]) - 1
ans = []
```

While the boundaries are valid:

```python
top <= bottom and left <= right
```

Read in four directions:

1. Top row: columns `left` to `right`.
2. Right column: rows `top` to `bottom`.
3. Bottom row: columns `right` to `left`, only if `top <= bottom`.
4. Left column: rows `bottom` to `top`, only if `left <= right`.

Return `ans`.

## Correctness

The algorithm keeps four boundaries around the unvisited part of the matrix.

Reading the top row visits every cell on the current top edge exactly once, then `top` moves inward. Reading the right column visits every cell on the current right edge exactly once, then `right` moves inward.

After those two moves, the remaining unvisited region may have no rows or no columns. The algorithm checks the boundaries before reading the bottom row and left column. This prevents duplicate visits in single-row and single-column cases.

Each loop removes one outer layer from the unvisited rectangle. Since every cell belongs to exactly one such layer, every cell is added once. The order of adding cells follows right, down, left, and up, so the returned list is exactly the spiral order.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(m * n)` | Every cell is visited once |
| Space | `O(1)` extra | Apart from the output list, only boundary variables are stored |

The output list stores `m * n` values, which is required by the problem.

## Implementation

```python
class Solution:
    def spiralOrder(self, matrix: list[list[int]]) -> list[int]:
        top = 0
        bottom = len(matrix) - 1
        left = 0
        right = len(matrix[0]) - 1

        ans = []

        while top <= bottom and left <= right:
            for col in range(left, right + 1):
                ans.append(matrix[top][col])
            top += 1

            for row in range(top, bottom + 1):
                ans.append(matrix[row][right])
            right -= 1

            if top <= bottom:
                for col in range(right, left - 1, -1):
                    ans.append(matrix[bottom][col])
                bottom -= 1

            if left <= right:
                for row in range(bottom, top - 1, -1):
                    ans.append(matrix[row][left])
                left += 1

        return ans
```

## Code Explanation

We start with the whole matrix as the unvisited rectangle:

```python
top = 0
bottom = len(matrix) - 1
left = 0
right = len(matrix[0]) - 1
```

The loop continues while there is still a valid rectangle:

```python
while top <= bottom and left <= right:
```

First, read the top row:

```python
for col in range(left, right + 1):
    ans.append(matrix[top][col])
top += 1
```

After reading it, that row is consumed, so `top` moves down.

Next, read the right column:

```python
for row in range(top, bottom + 1):
    ans.append(matrix[row][right])
right -= 1
```

After reading it, that column is consumed, so `right` moves left.

Before reading the bottom row, check that a row still remains:

```python
if top <= bottom:
```

Then read from right to left:

```python
for col in range(right, left - 1, -1):
    ans.append(matrix[bottom][col])
bottom -= 1
```

Before reading the left column, check that a column still remains:

```python
if left <= right:
```

Then read from bottom to top:

```python
for row in range(bottom, top - 1, -1):
    ans.append(matrix[row][left])
left += 1
```

When the boundaries cross, all cells have been visited.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.spiralOrder([
        [1, 2, 3],
        [4, 5, 6],
        [7, 8, 9],
    ]) == [1, 2, 3, 6, 9, 8, 7, 4, 5]

    assert s.spiralOrder([
        [1, 2, 3, 4],
        [5, 6, 7, 8],
        [9, 10, 11, 12],
    ]) == [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]

    assert s.spiralOrder([[1]]) == [1]

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

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

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

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `3 x 3` matrix | Standard square case |
| `3 x 4` matrix | Rectangular case |
| `1 x 1` matrix | Smallest input |
| Single row | Prevents duplicate bottom-row traversal |
| Single column | Prevents duplicate left-column traversal |
| `2 x 2` matrix | Small even-sized square case |