59. Spiral Matrix II
Model: qwen3.5:9b
Topics: Array
FAANG asked: 0
Acceptance rate: 58.2%
Problem Breakdown
We are given a positive integer n. Our goal is to construct an matrix where every cell contains a unique number from 1 up to . The numbers must be placed in “spiral order,” meaning we start at the top-left corner, move right across the first row, then down the last column, left along the bottom row, and finally up the first remaining column. This pattern repeats inward until all cells are filled.
Inputs:
n(integer): The dimension of the square matrix ().
Outputs:
- A list of lists representing the integer matrix.
Constraints & Edge Cases:
- Empty Input: Constraints guarantee , so we don’t need to handle empty matrices, but our logic should naturally support it if extended.
- Overflow: With Python’s arbitrary precision integers and max
n=20, values up to 400 fit easily in standard types; no overflow checks needed. - Single Element (): The spiral must handle the case where top, bottom, left, and right boundaries all start at index 0 without causing infinite loops or out-of-bounds errors.
Intuition
A brute-force approach might try to calculate coordinates for each number using complex modulo arithmetic based on layers (e.g., determining which “ring” of the spiral a cell belongs to). While mathematically possible ( per element), it is error-prone and harder to explain.
A better approach simulates the traversal process directly. Imagine we have four boundaries: top, bottom, left, and right. We fill cells starting from (0, 0) moving right until hitting right, then down until hitting bottom, etc., shrinking these boundaries after each pass (e.g., incrementing top once the top row is done).
This simulation approach naturally handles the spiral logic. The key insight is that we don’t need to know where a number should go; we just fill valid cells in order and shrink the active area until no more space remains. This reduces complexity significantly compared to coordinate math or sorting pre-generated lists ().
Approach
- Initialization: Create an matrix initialized with zeros (or placeholders) so we can track filled cells easily, though strictly speaking we just overwrite them sequentially from 1 to . Define four boundary indices:
top = 0,bottom = n - 1,left = 0,right = n - 1. - Traversal Loop: Use a counter starting at 1 (or iterate until the matrix is full). While boundaries are valid (
top <= bottomandleft <= right):- Fill Top Row: Iterate from
lefttoright, placing values in rowtop. Incrementtop. - Check Validity: If
top > bottom, the matrix is full (or we’ve crossed boundaries), so stop. - Fill Right Column: Iterate from
toptobottom, placing values in columnright. Decrementright. - Check Validity: If
left > right, stop. - Fill Bottom Row: Iterate from
rightdown toleft, placing values in rowbottom. Decrementbottom. - Check Validity: If
top > bottom, stop (though usually handled by loop condition). - Fill Left Column: Iterate from
bottomup totop, placing values in columnleft. Incrementleft.
- Fill Top Row: Iterate from
- Termination: The process stops when all cells are filled or boundaries cross, which happens exactly at the end of a spiral layer for odd/even dimensions alike.
Complexity Analysis
- Time Complexity: . We visit every cell in the matrix exactly once to assign it a value from 1 to . Since there are cells, this is linear with respect to the number of elements generated.
- Space Complexity: auxiliary (excluding output). The algorithm uses only four integer variables for boundaries and counters. If we count the result matrix itself as space complexity, it would be .
Solution
def generateMatrix(n):
# Initialize n x n matrix with 0s to hold values
matrix = [[0] * n for _ in range(n)]
# Define boundaries: top row index, bottom row index,
# left column index, right column index.
top, bottom = 0, n - 1
left, right = 0, n - 1
count = 1
total_cells = n * n
while count <= total_cells:
# Fill Top Row (Left -> Right)
for col in range(left, right + 1):
matrix[top][col] = count
count += 1
top += 1
if not (top <= bottom): break
# Fill Right Column (Top -> Bottom)
for row in range(top, bottom + 1):
matrix[row][right] = count
count += 1
right -= 1
if not (left <= right): break
# Fill Bottom Row (Right <- Left), check validity first to avoid double-filling on odd n center logic edge cases in loop structure
for col in range(right, left - 1, -1):
matrix[bottom][col] = count
count += 1
bottom -= 1
if not (top <= bottom): break
# Fill Left Column (Bottom -> Top)
for row in range(bottom, top - 1, -1):
matrix[row][left] = count
count += 1
left += 1
return matrix
Edge Cases Handled
- : The loop runs once. Top Row fills index (0,0).
topincrements to 1. Checktop <= bottom() fails immediately after incrementing or at start of next step logic preventing further access. Correctly returns[[1]]. - Odd : The center element is filled during the “Top Row” pass of the final iteration where boundaries converge, ensuring it isn’t missed by boundary checks that might prematurely stop a loop if not implemented carefully (handled here via explicit validity breaks).
- Max Constraint (): Python handles integer sizes effortlessly; no overflow occurs. The time ensures execution is well within limits for 400 operations.