Spiral Matrix II

The key distinction is simple: Spiral Matrix reads values from an existing grid; Spiral Matrix II constructs the grid while the spiral advances. The reliable solution allocates an empty matrix, tracks four inclusive boundaries, fills one side at a time, and shrinks the remaining rectangle.

For n = 3, the target is:

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

For n = 1, it is simply:

[[1]]

The input is a positive integer n with 1 <= n <= 20. The output must be an n x n matrix containing every integer from 1 through n² in clockwise spiral order.

Model the Unfilled Rectangle

A spiral matrix has a useful geometric property: after completing the outer ring, the remaining work is another, smaller rectangle.

Track that rectangle with four inclusive boundaries:

• top: first unfilled row
• bottom: last unfilled row
• left: first unfilled column
• right: last unfilled column

Initially, the unfilled rectangle is the whole matrix:

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

A single ring always follows the same four passes:

1. Top row, left to right
2. Right column, top to bottom
3. Bottom row, right to left
4. Left column, bottom to top

After each pass, move the corresponding boundary inward:

Pass	Direction	Boundary update
Top row	left → right	top += 1
Right column	top → bottom	right -= 1
Bottom row	right → left	bottom -= 1
Left column	bottom → top	left += 1

The matrix stores the output. The counter stores the next value to write. The boundaries prevent writes from leaking back into completed rings.

This is why I prefer boundary simulation here over a cursor plus direction array. A direction-based simulation can work: move right, turn down, turn left, turn up, and turn whenever the next cell is invalid or already occupied. But then the matrix contents become part of the control state. With boundaries, the geometry is explicit, and the uniqueness proof is much easier to inspect.

Derive the Four-Side Fill

Start with the outer rectangle. Write its top row from left to right, then shrink top. Write the right column from top to bottom, then shrink right.

The remaining bottom row or left column may no longer exist. This is the source of most boundary bugs.

For example, after writing the top row of a one-row region, top moves past bottom. A bottom-row loop must not run. Similarly, after the bottom pass, left may have crossed right, so the left-column loop must not run.

The algorithm is therefore:

while the remaining rectangle is nonempty:
    fill the top row
    move top inward

    fill the right column
    move right inward

    if a bottom row remains:
        fill the bottom row
        move bottom inward

    if a left column remains:
        fill the left column
        move left inward

The counter increases at every assignment:

matrix[row][column] = value
value += 1

That coupling matters. If the algorithm performs exactly n² valid assignments, the values written must be 1, 2, ..., n² with no gaps.

Prove Every Cell Is Written Once

Use this invariant:

Before each loop iteration, every cell outside the rectangle [top..bottom] x [left..right] is already filled correctly, and every cell inside it is still unassigned.

The first iteration satisfies the invariant because the entire matrix is unassigned.

Now consider one iteration:

• The top-row pass writes only row top, then increments top.
• The right-column pass writes only column right, within the remaining vertical range, then decrements right.
• The bottom-row pass runs only if top <= bottom. It writes the last remaining bottom boundary, then decrements bottom.
• The left-column pass runs only if left <= right. It writes the last remaining left boundary, then increments left.

Each completed boundary moves inward. Therefore, later iterations cannot write those cells again.

The guards are not cosmetic special cases. They are the overlap checks that make the proof work:

if top <= bottom:
    # bottom row still exists

if left <= right:
    # left column still exists

Completeness follows from the shrinking rectangle. Every assignment fills one previously unassigned cell. The boundaries continue moving inward until no rectangle remains. Since the matrix has n² cells, the algorithm performs exactly n² assignments.

That gives all three required properties:

1. No cell is written twice.
2. No cell is left unfilled.
3. The values are exactly 1 through n².

Dry-Run: The Odd Center

Take n = 3.

Initially:

top = 0, bottom = 2
left = 0, right = 2
value = 1

Fill the outer ring

Top row, left to right:

1  2  3
.  .  .
.  .  .

Now top = 1.

Right column, top to bottom:

1  2  3
.  .  4
.  .  5

Now right = 1.

Bottom row, right to left:

1  2  3
.  .  4
7  6  5

Now bottom = 1.

Left column, bottom to top:

1  2  3
8  .  4
7  6  5

Now left = 1.

The remaining rectangle is:

top = bottom = 1
left = right = 1

It contains exactly one cell. The next top-row pass writes 9:

1  2  3
8  9  4
7  6  5

After that pass, top = 2, so the rectangle is empty. The later column passes perform no writes.

For an even size such as n = 4, the final remaining region is 2 x 2, not a single center cell. The same four-pass logic still works. There is no separate “odd matrix” algorithm; the guards and inclusive boundaries handle both cases.

Before trusting an implementation, hand-check:

• n = 1: single-cell center
• n = 2: no duplicate side writes
• n = 3: odd center
• n = 4: inner 2 x 2 ring

Small cases expose pointer errors faster than large examples do.

Python Implementation: Keep State Visible

Here is a readable generate spiral matrix implementation using shrinking boundaries:

from typing import List


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:
            # Top row: left to right
            for column in range(left, right + 1):
                matrix[top][column] = value
                value += 1
            top += 1

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

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

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

        return matrix

Each variable has one job:

• matrix holds the required output.
• top, bottom, left, and right describe the still-unfilled rectangle.
• value guarantees increasing spiral assignment order.

The first two passes do not need explicit guards in this square problem because their ranges become empty when the remaining region has collapsed. The bottom and left passes use explicit checks because they are the passes most likely to overlap a row or column already consumed by the earlier passes. Keeping those checks visible is better than hiding them in compressed loop bounds.

For n = 3, the function returns:

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

This is matrix construction, not traversal. There is no input matrix to inspect and no result list to append to. Every value is generated and immediately assigned to its final coordinate.

Complexity and Interview Checks

The matrix contains n² cells, and each cell is written exactly once. Therefore:

• Time: O(n²)
• Output space: O(n²) for the returned matrix
• Auxiliary space: O(1) for the boundaries and counter

Be precise about the space claim. Saying the solution uses O(1) total space is incorrect if the required output matrix is included. The extra control state is constant, but the output itself necessarily grows with n².

Before submitting, check the implementation against these conditions:

1. The counter starts at 1.
2. The counter reaches n² + 1 after the final increment.
3. The top boundary moves downward.
4. The bottom boundary moves upward.
5. The left boundary moves rightward.
6. The right boundary moves leftward.
7. The bottom row is guarded by top <= bottom.
8. The left column is guarded by left <= right.
9. n = 1 writes the center exactly once.
10. Both odd and even sizes finish without overwriting a cell.

The transferable pattern is broader than this one matrix. When a grid problem follows concentric layers and each layer has a fixed ordered set of sides, represent the remaining rectangle with inclusive boundaries. Attach one boundary update to each side. Guard the passes that may disappear when dimensions collapse.

Then implement from the invariant, not from memory. Dry-run n = 1, 2, 3, and 4; watch the boundaries move; verify the counter. That is the difference between recognizing a spiral fill and merely hoping the loops line up.