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

Step 1: Understand the movement pattern
- The fill direction cycles right, down, left, and up.
- After finishing one side, the active unfilled rectangle becomes smaller.

Step 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

Step 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.

Step 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

Step 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]]`

Step 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?
Step 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.

Step 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

Step 1: Understand the movement pattern

Step 2: Brute-force with direction vectors and visited cells

Step 3: Shrink four boundaries instead of checking visited

Step 4: Fill one ring at a time

Step 5: Dry run / ring trace

Step 6: Common mistakes and follow-ups

Step 7: Edge cases to test mentally

Step 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

Spiral Matrix II – Solution & Complexity

Solution Walkthrough

1Step 1: Understand the movement pattern

2Step 2: Brute-force with direction vectors and visited cells

3Step 3: Shrink four boundaries instead of checking visited

4Step 4: Fill one ring at a time

5Step 5: Dry run / ring trace

6Step 6: Common mistakes and follow-ups

7Step 7: Edge cases to test mentally

8Step 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

Step 1: Understand the movement pattern

Step 2: Brute-force with direction vectors and visited cells

Step 3: Shrink four boundaries instead of checking visited

Step 4: Fill one ring at a time

Step 5: Dry run / ring trace

Step 6: Common mistakes and follow-ups

Step 7: Edge cases to test mentally

Step 8: Final full solution and complexity