LeetCode #59 Medium

Spiral Matrix II

Build an n x n matrix filled with 1 to n squared laid out in clockwise spiral order.

arraymatrixsimulation

02

Intuition

💡

This is Spiral Matrix with the arrows reversed, and it carries the same boundary bug with one nasty difference: here the bug is silent. In problem 54 a missing guard duplicates a value in the output list and you see it immediately. Here the sweeps write instead of read, so a wall you sweep twice simply overwrites a cell you already filled, and the finished grid still looks like a perfectly reasonable spiral. Nothing throws, nothing looks ragged, and a value is quietly missing while another appears twice. So do not trust the picture, trust the counter: check top <= bottom before the bottom sweep and left <= right before the left sweep, and then verify that the running value ends at exactly n squared plus one. The invariant is that the rectangle inside the four walls holds precisely the cells still unwritten, which is why writing into it can never destroy anything.

03

Approach

1

Allocate first, then walk the walls

Create the n x n grid of zeros up front. Unlike problem 54 there is no input to read, only positions to visit, so the four-boundary walk is purely a coordinate generator. Keep a single counter val starting at 1 and write val then increment it at every cell the walk touches.

2

Four sweeps, each retracting its own wall

Fill the top row left-to-right and raise top; the right column top-to-bottom and pull right in; the bottom row right-to-left and raise bottom; the left column bottom-to-top and push left in. Because the counter is monotonic, correctness reduces to visiting every cell exactly once, in the right order.

3

Guard the return sweeps, then count

Re-check top <= bottom before the bottom sweep and left <= right before the left sweep, exactly as in problem 54. Then use the counter as a self-test: after the loop, val must equal n squared plus one. If a guard were missing the walk would write more cells than the grid has, and that arithmetic catches the silent overwrite that your eyes will not.

04

Solution & live demo

python

▶1class Solution:
▶2    def generateMatrix(self, n: int) -> List[List[int]]:
▶3        grid = [[0] * n for _ in range(n)]
▶4        top, bottom, left, right = 0, n - 1, 0, n - 1
▶5        val = 1
▶6        while top <= bottom and left <= right:
▶7            for c in range(left, right + 1):
▶8                grid[top][c] = val
▶9                val += 1
▶10            top += 1
▶11            for r in range(top, bottom + 1):
▶12                grid[r][right] = val
▶13                val += 1
▶14            right -= 1
▶15            if top <= bottom:
▶16                for c in range(right, left - 1, -1):
▶17                    grid[bottom][c] = val
▶18                    val += 1
▶19                bottom -= 1
▶20            if left <= right:
▶21                for r in range(bottom, top - 1, -1):
▶22                    grid[r][left] = val
▶23                    val += 1
▶24                left += 1
▶25        return grid

05

Edge cases

n = 1

The top sweep writes the only cell, then both guards fail and the loop exits with val = 2.

n = 0

The while condition is false immediately and an empty list is returned.

Odd n, e.g. 3 or 5

The centre cell is a 1x1 remainder reached by the top sweep alone; the guards stop the return sweeps rewriting it.

Even n, e.g. 4

The innermost ring is a genuine 2x2, so all four sweeps run on it and no guard fires.

06

Complexity

Time

O(n^2)

Space

O(1)

The returned grid is the required output, so no auxiliary structure beyond four integers and a counter.