LeetCode 59 - Spiral Matrix II

The problem asks us to generate an n x n matrix and fill it with numbers from 1 to n^2 in spiral order. A spiral order traversal means we begin at the top-left corner and move in a clockwise pattern: 1. Move left to right across the top row 2.

leetcodemediumarraymatrixsimulation

LeetCode Problem 59

Difficulty: 🟡 Medium
Topics: Array, Matrix, Simulation

Solution

LeetCode 59 - Spiral Matrix II

Problem Understanding

The problem asks us to generate an n x n matrix and fill it with numbers from 1 to n^2 in spiral order.

A spiral order traversal means we begin at the top-left corner and move in a clockwise pattern:

  1. Move left to right across the top row
  2. Move top to bottom down the right column
  3. Move right to left across the bottom row
  4. Move bottom to top up the left column

After completing one outer layer, we continue the same process for the inner layer until every cell has been filled.

For example, when n = 3, the matrix should become:

1 2 3
8 9 4
7 6 5

The numbers increase sequentially while the direction changes whenever we reach a boundary.

The input is a single positive integer n. The output is a two-dimensional square matrix containing exactly the integers from 1 through n^2.

The constraint 1 <= n <= 20 tells us the matrix is fairly small. Even an O(n^2) solution is completely acceptable because the matrix itself contains n^2 elements, and every valid solution must at least write to every cell once.

Several edge cases are important:

  • n = 1, where the matrix contains only a single element
  • Small even-sized matrices such as n = 2, where there is no single center cell
  • Odd-sized matrices such as n = 3 or n = 5, where the spiral eventually reaches one central cell
  • Correctly updating boundaries after each directional traversal, because off-by-one mistakes are very common in matrix simulation problems

Approaches

Brute-Force Approach

A brute-force solution could simulate movement one step at a time while maintaining a direction array and checking whether the next position is valid. At each step, we attempt to continue moving in the current direction. If the next position is outside the matrix or already filled, we rotate to the next direction.

This approach works because it directly follows the spiral movement rules. We always place the next number into the current position and carefully decide when to turn.

Although this method is valid, it requires repeated boundary checking and visited-cell checking on every move. The implementation becomes slightly more complicated because we need either:

  • A visited matrix, or
  • Special marker values to indicate already-filled cells

The time complexity is still acceptable, but the logic is less elegant than a boundary-based approach.

Optimal Approach

The optimal approach uses four boundaries:

  • top
  • bottom
  • left
  • right

These boundaries describe the current unfilled rectangle inside the matrix.

Instead of moving one step at a time indefinitely, we fill one entire side of the current layer at once:

  • Fill the top row
  • Fill the right column
  • Fill the bottom row
  • Fill the left column

After finishing each side, we shrink the corresponding boundary inward.

This works particularly well because spiral traversal naturally processes the matrix layer by layer. Each iteration completes one outer ring before moving inward.

The approach is clean, avoids unnecessary visited tracking, and guarantees every cell is written exactly once.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n²) Uses visited tracking or direction simulation
Optimal O(n²) O(1) auxiliary space Uses shrinking boundaries for layer-by-layer filling

Algorithm Walkthrough

  1. Create an n x n matrix initialized with zeros. This matrix will eventually hold all numbers from 1 to n^2.
  2. Initialize four boundary variables:
  • top = 0
  • bottom = n - 1
  • left = 0
  • right = n - 1

These boundaries define the current rectangle that still needs to be filled. 3. Initialize a variable current = 1. This tracks the next number to insert into the matrix. 4. Fill the top row from left to right.

Iterate from left to right and place current into each cell. Increment current after every placement. 5. Move the top boundary downward by one.

The top row is now fully processed and should not be revisited. 6. Fill the right column from top to bottom.

Iterate from top to bottom and place numbers into the rightmost column. 7. Move the right boundary leftward by one.

The right column has now been completed. 8. Before continuing, check whether the boundaries are still valid.

This is important because odd-sized matrices can collapse into a single row or column. 9. Fill the bottom row from right to left.

Iterate backward from right to left. 10. Move the bottom boundary upward by one. 11. Fill the left column from bottom to top.

Iterate backward from bottom to top. 12. Move the left boundary rightward by one. 13. Repeat the process while left <= right and top <= bottom. 14. Once all layers are processed, return the matrix.

Why it works

The algorithm maintains the invariant that all cells outside the current boundaries have already been filled correctly, while all cells inside the boundaries remain unfilled.

Each iteration completely fills one outer layer of the spiral without overlapping previously filled cells. After processing a side, the corresponding boundary shrinks inward, reducing the remaining problem to a smaller submatrix.

Because every cell belongs to exactly one layer and is written exactly once, the final matrix contains all numbers from 1 to n^2 in the required spiral order.

Python Solution

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

        current = 1

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

            top += 1

            # Fill right column
            for row in range(top, bottom + 1):
                matrix[row][right] = current
                current += 1

            right -= 1

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

                bottom -= 1

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

                left += 1

        return matrix

The implementation begins by creating the result matrix filled with zeros. This provides placeholder values that will later be replaced during the spiral traversal.

The four boundary variables define the current active region of the matrix. Initially, they cover the entire matrix.

The while loop continues as long as there is still an unfilled region. Inside the loop, the algorithm processes the matrix in four directional passes:

  • Left to right across the top
  • Top to bottom down the right
  • Right to left across the bottom
  • Bottom to top up the left

After each directional traversal, the corresponding boundary is adjusted inward because that row or column is now complete.

The conditional checks before filling the bottom row and left column are important. Without them, small matrices or odd-sized center layers could cause duplicate writes or invalid indexing.

Finally, the completed matrix is returned.

Go Solution

func generateMatrix(n int) [][]int {
	matrix := make([][]int, n)

	for i := 0; i < n; i++ {
		matrix[i] = make([]int, n)
	}

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

	current := 1

	for left <= right && top <= bottom {
		// Fill top row
		for col := left; col <= right; col++ {
			matrix[top][col] = current
			current++
		}

		top++

		// Fill right column
		for row := top; row <= bottom; row++ {
			matrix[row][right] = current
			current++
		}

		right--

		// Fill bottom row
		if top <= bottom {
			for col := right; col >= left; col-- {
				matrix[bottom][col] = current
				current++
			}

			bottom--
		}

		// Fill left column
		if left <= right {
			for row := bottom; row >= top; row-- {
				matrix[row][left] = current
				current++
			}

			left++
		}
	}

	return matrix
}

The Go implementation follows exactly the same logic as the Python solution.

The main difference is matrix initialization. In Go, we explicitly allocate each row using make([]int, n).

Go slices are used instead of Python lists, but conceptually they behave similarly for this problem.

Integer overflow is not a concern because the maximum value written is 20^2 = 400, which easily fits within Go's standard integer type.

Worked Examples

Example 1

Input:

n = 3

Initial matrix:
0 0 0
0 0 0
0 0 0

Initial state:

Variable Value
top 0
bottom 2
left 0
right 2
current 1

Step 1: Fill top row

Fill row 0 from column 0 to 2.

Matrix:
1 2 3
0 0 0
0 0 0

Update:

top = 1
current = 4

Step 2: Fill right column

Fill column 2 from row 1 to 2.

Matrix:
1 2 3
0 0 4
0 0 5

Update:

right = 1
current = 6

Step 3: Fill bottom row

Fill row 2 from column 1 to 0.

Matrix:
1 2 3
0 0 4
7 6 5

Update:

bottom = 1
current = 8

Step 4: Fill left column

Fill column 0 from row 1 to 1.

Matrix:
1 2 3
8 0 4
7 6 5

Update:

left = 1
current = 9

Step 5: Fill center

Only one cell remains.

Matrix:
1 2 3
8 9 4
7 6 5

Final output:

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

Example 2

Input:

n = 1

Initial matrix:
0

The algorithm fills the single top row immediately.

Final matrix:
1

Output:

[[1]]

Complexity Analysis

Measure Complexity Explanation
Time O(n²) Every cell in the matrix is written exactly once
Space O(1) auxiliary space Only boundary variables and counters are used, excluding output matrix

The algorithm processes each matrix position exactly one time. Since there are n^2 cells, the total runtime is O(n^2).

The extra working memory is constant because the algorithm only stores a few integer variables for boundaries and counters. The output matrix itself is required by the problem and is not counted as auxiliary space.

Test Cases

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

        current = 1

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

            top += 1

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

            right -= 1

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

                bottom -= 1

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

                left += 1

        return matrix

solution = Solution()

assert solution.generateMatrix(1) == [[1]]  # Smallest possible matrix

assert solution.generateMatrix(2) == [
    [1, 2],
    [4, 3]
]  # Small even-sized matrix

assert solution.generateMatrix(3) == [
    [1, 2, 3],
    [8, 9, 4],
    [7, 6, 5]
]  # Example from problem statement

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

assert solution.generateMatrix(5) == [
    [1, 2, 3, 4, 5],
    [16, 17, 18, 19, 6],
    [15, 24, 25, 20, 7],
    [14, 23, 22, 21, 8],
    [13, 12, 11, 10, 9]
]  # Larger odd-sized matrix
Test Why
n = 1 Verifies smallest valid input
n = 2 Verifies even-sized spiral behavior
n = 3 Verifies standard spiral formation
n = 4 Verifies multiple complete layers
n = 5 Verifies odd-sized matrix with center cell

Edge Cases

Single Cell Matrix

When n = 1, the matrix contains only one cell. This case can expose boundary-update bugs because the algorithm immediately reaches the center.

The implementation handles this correctly because the top-row traversal fills the single cell, after which the boundaries invalidate naturally and terminate the loop safely.

Odd-Sized Matrices

Odd-sized matrices eventually reduce to a single center cell. If boundary checks are missing, the algorithm might overwrite cells or attempt invalid traversals after the center has already been filled.

The conditions:

if top <= bottom:

and

if left <= right:

prevent duplicate processing when the spiral collapses inward.

Even-Sized Matrices

Even-sized matrices do not have a single center cell. Instead, the spiral ends after processing a final 2 x 2 region.

This can cause off-by-one mistakes if boundaries are updated in the wrong order. The implementation updates boundaries immediately after finishing each side, which guarantees the next traversal only touches unfilled cells.