Domain 2MediumCORE

Spiral Matrix II

We are given a positive integer n. Our goal is to construct an $n times n$ matrix where every cell contains a unique number from 1 up to $n^2$. 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.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Array

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 n×nn \times n matrix where every cell contains a unique number from 1 up to n2n^2. 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 (1≤n≤201 \le n \le 20).

Outputs:

  • A list of lists representing the n×nn \times n integer matrix.

Constraints & Edge Cases:

  • Empty Input: Constraints guarantee n≥1n \ge 1, 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 (n=1n=1): 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 k∈[1,n2]k \in [1, n^2] using complex modulo arithmetic based on layers (e.g., determining which “ring” of the spiral a cell belongs to). While mathematically possible (O(1)O(1) 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 (O(N2log⁡N)O(N^2 \log N)).

Approach

  1. Initialization: Create an n×nn \times n matrix initialized with zeros (or placeholders) so we can track filled cells easily, though strictly speaking we just overwrite them sequentially from 1 to n2n^2. Define four boundary indices: top = 0, bottom = n - 1, left = 0, right = n - 1.
  2. Traversal Loop: Use a counter starting at 1 (or iterate until the matrix is full). While boundaries are valid (top <= bottom and left <= right):
    • Fill Top Row: Iterate from left to right, placing values in row top. Increment top.
    • Check Validity: If top > bottom, the matrix is full (or we’ve crossed boundaries), so stop.
    • Fill Right Column: Iterate from top to bottom, placing values in column right. Decrement right.
    • Check Validity: If left > right, stop.
    • Fill Bottom Row: Iterate from right down to left, placing values in row bottom. Decrement bottom.
    • Check Validity: If top > bottom, stop (though usually handled by loop condition).
    • Fill Left Column: Iterate from bottom up to top, placing values in column left. Increment left.
  3. Termination: The process stops when all n2n^2 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: O(n2)O(n^2). We visit every cell in the matrix exactly once to assign it a value from 1 to n2n^2. Since there are n×nn \times n cells, this is linear with respect to the number of elements generated.
  • Space Complexity: O(1)O(1) 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 O(n2)O(n^2).

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

  • n=1n=1: The loop runs once. Top Row fills index (0,0). top increments to 1. Check top <= bottom (1≤01 \le 0) fails immediately after incrementing or at start of next step logic preventing further access. Correctly returns [[1]].
  • Odd nn: 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 (n=20n=20): Python handles integer sizes effortlessly; no overflow occurs. The O(n2)O(n^2) time ensures execution is well within limits for 400 operations.