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
- Maintain four boundaries
top,bottom,left,rightand fill the matrix one layer at a time. - 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.
- Shrink the corresponding boundary after each pass so the next pass works on the inner layer.
- The two
ifguards 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
nthe final single cell would be written twice, corrupting the counter. - Incrementing
valafter 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.