Spiral Matrix II

Balanced Binary Tree

Set Matrix Zeroes

Generate an n-by-n matrix filled from 1 through n² in clockwise spiral order.

Given an integer `n`, generate an `n x n` matrix filled with the numbers `1` through `n^2` in clockwise spiral order.

Start at the top-left corner, move right first, and keep turning clockwise whenever you would leave the current unfilled region.

**Input / output**
- Input: `n: int`
- Output: `int[][]`

**Examples**
1. `n = 1` returns `[[1]]`.
2. `n = 3` returns `[[1,2,3],[8,9,4],[7,6,5]]`.
3. `n = 4` returns `[[1,2,3,4],[12,13,14,5],[11,16,15,6],[10,9,8,7]]`.

**Constraints**
- `1 <= n <= 20`

**Follow-up**
Can you describe the loop invariant for the four shrinking boundaries, and why odd-sized matrices do not need a special center-case branch?

- The fill direction cycles right, down, left, and up.
- After finishing one side, the active unfilled rectangle becomes smaller.

Understand the movement pattern

- Keep a direction index and turn whenever the next cell would be out of bounds or already filled.
- This is straightforward, but it needs an extra visited-state check on every step.

Brute-force with direction vectors and visited cells

- Because the matrix is always square and we fill complete outer rings, we can track just `top`, `bottom`, `left`, and `right`.
- That avoids a visited check on every move and makes the control flow more interview-friendly.

Shrink four boundaries instead of checking visited

- Write the top row, right column, bottom row, and left column, then move all four boundaries inward.
- The same loop naturally handles the final center cell for odd `n`.

Fill one ring at a time

Trace `n = 3`.

| ring action | matrix state |
|---|---|
| fill top row | `[[1,2,3],[0,0,0],[0,0,0]]` |
| fill right column | `[[1,2,3],[0,0,4],[0,0,5]]` |
| fill bottom row backward | `[[1,2,3],[0,0,4],[7,6,5]]` |
| fill left column upward | `[[1,2,3],[8,0,4],[7,6,5]]` |
| next inner ring | `[[1,2,3],[8,9,4],[7,6,5]]` |

Dry run / ring trace

- Forgetting to guard the bottom-row and left-column passes after shrinking boundaries.
- Turning direction too early or too late in the visited-matrix approach.
- Off-by-one errors on inclusive boundary loops.
- Follow-up: how would you adapt the same idea to generate an `m x n` spiral instead of a square only?

Common mistakes and follow-ups

- `n = 1` should return a single-cell matrix.
- `n = 2` is the smallest case that touches all four directions.
- Odd `n` leaves one center cell, which the same boundary loop fills naturally.
- Larger `n` just repeats the same ring logic.

Edge cases to test mentally

Shrink four boundaries while filling one outer ring per loop. Every cell is written exactly once, so time is `O(n^2)` and the returned matrix uses `O(n^2)` space.