⚡Flashcard Drill➔
NeetCode #903LC-59MediumMath & Geometry
← Back to All Problems

#903 · #59 · Spiral Matrix II(螺旋矩阵 II)

📌 Problem Statement & Constraints

Given a positive integer n, generate an n x n matrix filled with the numbers 1 through n^2 arranged in spiral order, starting at the top-left and moving clockwise inward. Constraints: 1 <= n <= 20.

💡 Core Algorithmic Approaches

  1. Maintain four boundaries top, bottom, left, right and fill the matrix one layer at a time.
  2. Fill the top row left to right, the right column top to bottom, the bottom row right to left, and the left column bottom to top, advancing a counter as each cell is written.
  3. Shrink the corresponding boundary after each pass so the next pass works on the inner layer.
  4. The two if guards before the bottom-row and left-column passes prevent overwriting cells in a degenerate layer that has only one row or one column remaining.

💻 Benchmark Python3 Implementation

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        res = [[0] * n for _ in range(n)]
        top, bottom, left, right = 0, n - 1, 0, n - 1
        val = 1
        while top <= bottom and left <= right:
            for j in range(left, right + 1):          # top row
                res[top][j] = val
                val += 1
            top += 1
            for i in range(top, bottom + 1):          # right column
                res[i][right] = val
                val += 1
            right -= 1
            if top <= bottom:                         # a row still remains
                for j in range(right, left - 1, -1):
                    res[bottom][j] = val
                    val += 1
                bottom -= 1
            if left <= right:                         # a column still remains
                for i in range(bottom, top - 1, -1):
                    res[i][left] = val
                    val += 1
                left += 1
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n^2): each of the n^2 cells is written exactly once.
💾 Space Complexity
O(n^2): the output matrix (O(1) beyond it).

⚠️ Interview Pitfalls & Follow-ups

  • Omitting the boundary guards: for odd n the final single cell would be written twice, corrupting the counter.
  • Incrementing val after shrinking the boundary: the counter must advance once per written cell.
  • Using range(left, right) without +1: the right boundary is inclusive.
  • Filling the bottom row left-to-right: the spiral traverses it right-to-left, so the range must step by -1.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Math & Geometry Problems