# LeetCode 59: Spiral Matrix II

## Problem Restatement

We are given a positive integer `n`.

We need to generate an `n x n` matrix filled with numbers from `1` to `n^2` in spiral order.

The spiral starts at the top-left cell and moves:

1. Right
2. Down
3. Left
4. Up

Then it repeats inward until every cell is filled.

The official constraint is `1 <= n <= 20`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A positive integer `n` |
| Output | An `n x n` matrix |
| Values | Integers from `1` to `n^2` |
| Fill order | Clockwise spiral from the top-left corner |

Function shape:

```python
def generateMatrix(n: int) -> list[list[int]]:
    ...
```

## Examples

For:

```python
n = 3
```

The answer is:

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

The filling order is:

```text
1 -> 2 -> 3
          |
8 -> 9    4
|         |
7 <- 6 <- 5
```

For:

```python
n = 1
```

The answer is:

```python
[[1]]
```

There is only one cell, so we place `1`.

## First Thought: Simulate Movement

One approach is to walk through the matrix cell by cell.

Start at `(0, 0)`, move right, and place increasing numbers. When the next cell is outside the matrix or already filled, turn clockwise.

This works, but it needs extra checks against filled cells.

A boundary-based method is easier to explain and less error-prone.

## Key Insight

The matrix can be filled layer by layer.

Each layer has four boundaries:

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

For each layer:

1. Fill the top row from left to right.
2. Move `top` down.
3. Fill the right column from top to bottom.
4. Move `right` left.
5. Fill the bottom row from right to left.
6. Move `bottom` up.
7. Fill the left column from bottom to top.
8. Move `left` right.

Since the matrix is square, this process eventually reaches the center.

## Algorithm

Create an empty matrix filled with zeros:

```python
matrix = [[0] * n for _ in range(n)]
```

Initialize boundaries:

```python
top = 0
bottom = n - 1
left = 0
right = n - 1
```

Initialize the next value:

```python
value = 1
```

While the boundaries are still valid:

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

Fill the current outer layer in four directions.

After writing each number, increment `value`.

Return the filled matrix.

## Correctness

The algorithm maintains a rectangle of unfilled cells bounded by `top`, `bottom`, `left`, and `right`.

During each loop, it fills the outer edge of that rectangle in clockwise order. After the top row is filled, `top` moves inward. After the right column is filled, `right` moves inward. The same happens for the bottom row and left column.

No filled row or column is visited again because each boundary moves inward immediately after that edge is filled.

Every loop removes one outer layer from the unfilled region. Since the matrix has finitely many layers, the process ends after all cells are filled.

The value starts at `1` and increases by one after each cell write. Since the matrix has `n^2` cells and each cell is written once, the final matrix contains exactly the numbers from `1` to `n^2` in clockwise spiral order.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n^2)` | The matrix has `n^2` cells, and each cell is filled once |
| Space | `O(1)` extra | Apart from the returned matrix, only a few variables are used |

The returned matrix itself uses `O(n^2)` space.

## Implementation

```python
class Solution:
    def generateMatrix(self, n: int) -> list[list[int]]:
        matrix = [[0] * n for _ in range(n)]

        top = 0
        bottom = n - 1
        left = 0
        right = n - 1

        value = 1

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

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

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

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

        return matrix
```

## Code Explanation

We first create the result matrix:

```python
matrix = [[0] * n for _ in range(n)]
```

Then define the current unfilled rectangle:

```python
top = 0
bottom = n - 1
left = 0
right = n - 1
```

The next number to place is:

```python
value = 1
```

The loop continues while at least one row and one column remain:

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

First, fill the top row:

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

Then fill the right column:

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

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

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

Then fill it from right to left:

```python
for col in range(right, left - 1, -1):
    matrix[bottom][col] = value
    value += 1
bottom -= 1
```

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

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

Then fill it from bottom to top:

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

When the boundaries cross, all cells have been filled.

## Testing

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

    assert s.generateMatrix(1) == [
        [1],
    ]

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

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

    assert s.generateMatrix(4) == [
        [1, 2, 3, 4],
        [12, 13, 14, 5],
        [11, 16, 15, 6],
        [10, 9, 8, 7],
    ]

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `n = 1` | Smallest input |
| `n = 2` | Small even-sized matrix |
| `n = 3` | Standard example with center cell |
| `n = 4` | Larger even-sized matrix |