[Medium] 59. Spiral Matrix II

Problem Statement

Given a positive integer n, generate an n × n matrix filled with elements from 1 to n² in spiral order (clockwise).

Examples

Example 1:

Input: n = 3
Output:
1  2  3
8  9  4
7  6  5

Example 2:

Input: n = 1
Output: [[1]]

Constraints

  • 1 <= n <= 20

Clarification Questions

  1. Direction: Clockwise from top-left? (Assumption: Yes — right, down, left, up.)
  2. Starting value: Fill from 1 to n²? (Assumption: Yes.)
  3. n = 1: Return [[1]]? (Assumption: Yes.)
  4. Matrix type: 2D list of integers? (Assumption: Yes.)
  5. In-place: Generate into new matrix? (Assumption: Yes, return new matrix.)

Interview Deduction Process (20 minutes)

Step 1: Simulation (5 min) — Maintain boundaries (top, bottom, left, right). Fill top row left→right, right col top→bottom, bottom row right→left (if different from top), left col bottom→top (if different from right). Shrink boundaries. Repeat.

Step 2: Layer-by-layer (7 min) — Same idea; for each layer fill four sides in order. Handle n odd (center cell) and n even (no center). O(n²) time and space.

Step 3: Optimized (8 min) — Single loop with direction vector; change direction when hitting boundary or already-filled cell. Alternatively keep boundary variables; both are O(n²).

Solution Approach

Core Observations

  • The matrix is square
  • We fill numbers 1 → n² in a clockwise spiral
  • This is a simulation problem – no DP or graph tricks, just precise boundary control

Layer-by-Layer (Boundary Shrinking)

Think of the matrix as concentric layers (rings). There are ⌈n/2⌉ layers. For each layer, fill four sides in order:

  1. Left → Right (top row of this layer)
  2. Top → Bottom (right column)
  3. Right → Left (bottom row)
  4. Bottom → Top (left column)

After each complete ring, shrink inward to the next layer.

Walk-Through (n = 4)

Layer 0:  1  2  3  4    Layer 1:  .  .  .  .
         12  .  .  5              .  6  7  .
         11  .  .  6              . 10  .  .
         10  9  8  7              .  9  .  .

Layer 0 fills the outer ring (1–12)
Layer 1 fills the inner ring (13–16)

Why Layer Index Works

For layer k:

  • Top-left corner is at (k, k)
  • Bottom-right corner is at (n-k-1, n-k-1)
  • Each of the four sides has carefully adjusted start/end to avoid double-counting corners

Approach: Layer-by-Layer – $O(n^2)$

Iterate over layers from 0 to (n+1)/2 - 1. For each layer, fill the four sides with incrementing counter.

class Solution:
    def generateMatrix(self, n):
        rtn = [[0] * n for _ in range(n)]
        cnt = 1
        
        for layer in range((n + 1) // 2):
            # top row (left → right)
            for ptr in range(layer, n - layer):
                rtn[layer][ptr] = cnt
                cnt += 1
            
            # right column (top → bottom)
            for ptr in range(layer + 1, n - layer):
                rtn[ptr][n - layer - 1] = cnt
                cnt += 1
            
            # bottom row (right → left)
            for ptr in range(n - layer - 2, layer - 1, -1):
                rtn[n - layer - 1][ptr] = cnt
                cnt += 1
            
            # left column (bottom → top)
            for ptr in range(n - layer - 2, layer, -1):
                rtn[ptr][layer] = cnt
                cnt += 1
        
        return rtn

Time: $O(n^2)$ – each cell filled exactly once Space: $O(n^2)$ for the output matrix (no extra space)

Alternative: Direction Array Simulation

Instead of explicit layer logic, use direction vectors and rotate when hitting a boundary or an already-filled cell. Often shorter code.

class Solution:
    def generateMatrix(self, n):
        mat = [[0] * n for _ in range(n)]
        
        # right, down, left, up
        dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        
        d = 0  # direction index
        r, c = 0, 0
        
        for num in range(1, n * n + 1):
            mat[r][c] = num
            
            nr = r + dirs[d][0]
            nc = c + dirs[d][1]
            
            # change direction if out of bounds or already filled
            if nr < 0 or nr >= n or nc < 0 or nc >= n or mat[nr][nc] != 0:
                d = (d + 1) % 4
                nr = r + dirs[d][0]
                nc = c + dirs[d][1]
            
            r, c = nr, nc
        
        return mat

Time: $O(n^2)$ Space: $O(n^2)$

Common Mistakes

  • Double-filling the center: when n is odd, the center cell belongs to only one side
  • Off-by-one on boundaries: each side must carefully exclude the corners already filled by the previous side
  • Wrong loop bounds on the return sides: the “right → left” and “bottom → top” loops start at n - layer - 2, not n - layer - 1

Key Takeaways

  • This is a pure implementation accuracy problem – recognize it as spiral simulation immediately
  • Layer-by-layer is safer and more explicit about boundaries
  • Direction array is shorter but requires checking “already filled” cells
  • Both approaches are $O(n^2)$ and optimal since every cell must be visited

Template Reference