59. Spiral Matrix II - Explanation

Description

You are given a positive integer n, generate an n x n matrix filled with elements from 1 to (n^2) in spiral order.

Example 1:

Input: n = 3

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

Example 2:

Input: n = 2

Output: [[1,2],[4,3]]

Example 3:

Input: n = 1

Output: [[1]]

Constraints:

1 <= n <= 20

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Iteration

Intuition

We fill an n x n matrix with values from 1 to n^2 in spiral order. Think of peeling an onion layer by layer. We maintain four boundaries (top, bottom, left, right) and fill each layer by moving right along the top row, down the right column, left along the bottom row, and up the left column. After completing each direction, we shrink the corresponding boundary inward.

Algorithm

Initialize an n x n matrix with zeros and set boundaries: left = 0, right = n - 1, top = 0, bottom = n - 1.
Start with val = 1 and continue while left <= right:
- Fill the top row from left to right, then increment top.
- Fill the right column from top to bottom, then decrement right.
- Fill the bottom row from right to left, then decrement bottom.
- Fill the left column from bottom to top, then increment left.
Return the filled matrix.

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        mat = [[0] * n for _ in range(n)]
        left, right = 0, n - 1
        top, bottom = 0, n - 1
        val = 1

        while left <= right:
            # Fill every val in top row
            for c in range(left, right + 1):
                mat[top][c] = val
                val += 1
            top += 1

            # Fill every val in right col
            for r in range(top, bottom + 1):
                mat[r][right] = val
                val += 1
            right -= 1

            # Fill every val in bottom row (reverse order)
            for c in range(right, left - 1, -1):
                mat[bottom][c] = val
                val += 1
            bottom -= 1

            # Fill every val in the left col (reverse order)
            for r in range(bottom, top - 1, -1):
                mat[r][left] = val
                val += 1
            left += 1

        return mat

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n ^ 2)$ for the output matrix.

2. Recursion

Intuition

The recursive approach mirrors the iterative one but uses function calls to handle each layer. We fill one complete ring of the spiral (top row, right column, bottom row, left column) and then recursively fill the inner portion. The base case is when the boundaries cross, meaning the entire matrix is filled.

Algorithm

Create a helper function fill(left, right, top, bottom, val) that fills one layer.
Base case: if left > right or top > bottom, return.
Fill the current layer in four directions (same as iterative approach), updating val after each cell.
After filling the outer ring, recursively call fill with updated boundaries for the inner layer.
Start the recursion with fill(0, n - 1, 0, n - 1, 1).

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        mat = [[0] * n for _ in range(n)]

        def fill(left, right, top, bottom, val):
            if left > right or top > bottom:
                return

            # Fill every val in top row
            for c in range(left, right + 1):
                mat[top][c] = val
                val += 1
            top += 1

            # Fill every val in right col
            for r in range(top, bottom + 1):
                mat[r][right] = val
                val += 1
            right -= 1

            # Fill every val in bottom row (reverse order)
            for c in range(right, left - 1, -1):
                mat[bottom][c] = val
                val += 1
            bottom -= 1

            # Fill every val in the left col (reverse order)
            for r in range(bottom, top - 1, -1):
                mat[r][left] = val
                val += 1
            left += 1

            # Recur for the inner layer
            fill(left, right, top, bottom, val)

        fill(0, n - 1, 0, n - 1, 1)
        return mat

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity:
- $O(n)$ space for recursion stack.
- $O(n ^ 2)$ space for the output matrix.

3. Iteration (Optimal)

Intuition

Instead of tracking four boundaries, we can use direction vectors to navigate the spiral. We start moving right and change direction (right -> down -> left -> up -> right...) whenever we hit a boundary or an already-filled cell. The direction change follows the pattern of rotating 90 degrees clockwise, which can be computed mathematically: if current direction is (dr, dc), the next direction is (dc, -dr).

Algorithm

Initialize an n x n matrix with zeros. Set starting position (r, c) = (0, 0) and direction (dr, dc) = (0, 1) (moving right).
For each value from 1 to n^2:
- Place the value at position (r, c).
- Check if the next position (with wraparound) is already filled.
- If so, rotate direction by setting (dr, dc) = (dc, -dr).
- Move to the next position: r += dr, c += dc.
Return the filled matrix.

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        mat = [[0] * n for _ in range(n)]
        r = c = 0
        dr, dc = 0, 1

        for val in range(n * n):
            mat[r][c] = val + 1
            if mat[(r + dr) % n][(c + dc) % n] != 0:
                dr, dc = dc, -dr
            r, c = r + dr, c + dc

        return mat

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n ^ 2)$ for the output matrix.

Common Pitfalls

Incorrect Boundary Updates

Failing to update boundaries (top, bottom, left, right) after filling each edge leads to overwriting previously filled cells or skipping cells entirely. Each boundary must be adjusted immediately after its corresponding edge is filled.

Off-by-One in Range Calculations

When iterating along rows or columns, using inclusive vs exclusive bounds incorrectly causes cells to be missed or written twice. For example, after filling the top row from left to right, the next column fill should start from top + 1, not top.

Forgetting to Handle Odd-Sized Matrices

For odd values of n, the center cell requires special attention. If the loop condition or boundary updates are off, the center cell may be skipped or the loop may not terminate correctly. The direction-based approach handles this naturally, but boundary-based approaches need careful loop conditions.