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

Function shape:

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

Examples

For:

n = 3

The answer is:

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

The filling order is:

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

For:

n = 1

The answer is:

[[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:

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:

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

Initialize boundaries:

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

Initialize the next value:

value = 1

While the boundaries are still valid:

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

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

Implementation

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:

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

Then define the current unfilled rectangle:

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

The next number to place is:

value = 1

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

while top <= bottom and left <= right:

First, fill the top row:

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

Then fill the right column:

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:

if top <= bottom:

Then fill it from right to left:

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:

if left <= right:

Then fill it from bottom to top:

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

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()