Spiral Matrix II – Solution & Complexity

Q: What is the time and space complexity of Spiral Matrix II?

The optimal Spiral Matrix II solution runs in `O(n^2)` time and `O(n^2)` space. Fill the matrix ring by ring while shrinking top, bottom, left, and right boundaries.

Q: What is the most efficient way to solve Spiral Matrix II?

Fill the matrix ring by ring while shrinking top, bottom, left, and right boundaries. This gives `O(n^2)` time complexity, and is a classic arrays, matrix, and simulation problem.

Q: How do you solve Spiral Matrix II in Python, JavaScript, Java, Go, Rust, C++ & Ruby?

We provide a worked Spiral Matrix II solution in Python, JavaScript, Java, Go, Rust, C++ & Ruby with a step-by-step explanation above. You can also open the interactive editor to write and run your own Python solution against the test cases in the browser.

Q: Is Spiral Matrix II an easy or hard interview question?

Spiral Matrix II is generally rated **Medium**. It tests arrays, matrix, and simulation, which are common coding-interview patterns.

Solution Walkthrough

1. Understand the movement pattern

The fill direction cycles right, down, left, and up.
After finishing one side, the active unfilled rectangle becomes smaller.

2. Brute-force with direction vectors and visited cells

Keep a direction index and turn whenever the next cell would be out of bounds or already filled.
This is straightforward, but it needs an extra visited-state check on every step.

def generate_matrix(n: int) -> list[list[int]]:
    matrix = [[0] * n for _ in range(n)]
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    row = col = direction = 0
    for value in range(1, n * n + 1):
        matrix[row][col] = value
        dr, dc = directions[direction]
        next_row = row + dr
        next_col = col + dc
        if not (0 <= next_row < n and 0 <= next_col < n) or matrix[next_row][next_col] != 0:
            direction = (direction + 1) % 4
            dr, dc = directions[direction]
            next_row = row + dr
            next_col = col + dc
        row, col = next_row, next_col
    return matrix

3. Shrink four boundaries instead of checking visited

Because the matrix is always square and we fill complete outer rings, we can track just top, bottom, left, and right.
That avoids a visited check on every move and makes the control flow more interview-friendly.

4. Fill one ring at a time

Write the top row, right column, bottom row, and left column, then move all four boundaries inward.
The same loop naturally handles the final center cell for odd n.

def generate_matrix(n: int) -> list[list[int]]:
    if n <= 0:
        return []
    matrix = [[0] * n for _ in range(n)]
    top, bottom = 0, n - 1
    left, right = 0, 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

5. Dry run / ring trace

Trace n = 3.

ring action	matrix state
fill top row	`[[1,2,3],[0,0,0],[0,0,0]]`
fill right column	`[[1,2,3],[0,0,4],[0,0,5]]`
fill bottom row backward	`[[1,2,3],[0,0,4],[7,6,5]]`
fill left column upward	`[[1,2,3],[8,0,4],[7,6,5]]`
next inner ring	`[[1,2,3],[8,9,4],[7,6,5]]`

6. Common mistakes and follow-ups

Forgetting to guard the bottom-row and left-column passes after shrinking boundaries.
Turning direction too early or too late in the visited-matrix approach.
Off-by-one errors on inclusive boundary loops.
Follow-up: how would you adapt the same idea to generate an m x n spiral instead of a square only?

7. Edge cases to test mentally

n = 1 should return a single-cell matrix.
n = 2 is the smallest case that touches all four directions.
Odd n leaves one center cell, which the same boundary loop fills naturally.
Larger n just repeats the same ring logic.

8. Final full solution and complexity

Shrink four boundaries while filling one outer ring per loop. Every cell is written exactly once, so time is O(n^2) and the returned matrix uses O(n^2) space.

def generate_matrix(n: int) -> list[list[int]]:
    if n <= 0:
        return []

    matrix = [[0] * n for _ in range(n)]
    top, bottom = 0, n - 1
    left, right = 0, 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

Spiral Matrix II – Solution & Complexity

Solution Walkthrough

1. Understand the movement pattern

2. Brute-force with direction vectors and visited cells

3. Shrink four boundaries instead of checking visited

4. Fill one ring at a time

5. Dry run / ring trace

6. Common mistakes and follow-ups

7. Edge cases to test mentally

8. Final full solution and complexity

FAQ

What is the time and space complexity of Spiral Matrix II?

What is the most efficient way to solve Spiral Matrix II?

How do you solve Spiral Matrix II in Python, JavaScript, Java, Go, Rust, C++ & Ruby?

Is Spiral Matrix II an easy or hard interview question?

See also