LeetCode 59: Spiral Matrix II Solution in Python Explained

Problem Statement

LeetCode 59, Spiral Matrix II, is a medium-level problem where you’re given an integer n. Your task is to generate an (n \times n) matrix filled with elements from 1 to (n^2) in spiral order, moving clockwise from the top-left corner inward. Return the resulting matrix as a 2D list of integers.

Constraints

  • 1 <= n <= 20: Matrix size is between 1 and 20.

Example

Input: n = 3
Output: [[1,2,3],[8,9,4],[7,6,5]]
Explanation: Spiral order:
1→2→3
↓     ↓
8  9→4
↑     ↓
7←6←5

Input: n = 1
Output: [[1]]
Explanation: 1x1 matrix with value 1.

Input: n = 4
Output: [[1,2,3,4],[12,13,14,5],[11,16,15,6],[10,9,8,7]]
Explanation: 4x4 spiral matrix.

Understanding the Problem

How do you solve LeetCode 59: Spiral Matrix II in Python? For n = 3, create a 3x3 matrix filled with 1 to 9 in spiral order: [[1,2,3],[8,9,4],[7,6,5]]. We need to place numbers sequentially while moving right, down, left, and up, spiraling inward. We’ll explore two approaches: a Layer-by-Layer Generation Solution (optimal and primary) and an Alternative with Direction Array (intuitive but more complex). The layer-by-layer method runs in O(n^2) time with O(1) extra space, building the matrix directly.

Solution 1: Layer-by-Layer Generation Approach (Primary)

Explanation

Generate the matrix layer by layer, using four boundaries (top, bottom, left, right) to define each spiral layer. Fill numbers in the order right, down, left, up, incrementing a counter, and shrink the boundaries inward until all (n^2) elements are placed.

Here’s a flow for (n = 3):

Layer 1: 1→2→3→4→5→6→7
Layer 2: 8→9
Result: [[1,2,3],[8,9,4],[7,6,5]]
  1. Initialize Matrix and Boundaries.
  • Create \(n \times n\) matrix, set top = 0, bottom = n-1, left = 0, right = n-1.
  1. Fill Layers.
  • Traverse right, down, left, up, increment value.
  1. Shrink Boundaries.
  • Move inward after each layer.
  1. Return Matrix.

Step-by-Step Example

Example 1: n = 3

We need [[1,2,3],[8,9,4],[7,6,5]].

  • Goal: Generate 3x3 spiral matrix.
  • Result for Reference: [[1,2,3],[8,9,4],[7,6,5]].
  • Start: n = 3, matrix = [[0,0,0],[0,0,0],[0,0,0]], val = 1, top = 0, bottom = 2, left = 0, right = 2.
  • Step 1: First layer.
    • Right: (0,0)=1, (0,1)=2, (0,2)=3, val = 4, top = 1.
    • Down: (1,2)=4, (2,2)=5, val = 6, right = 1.
    • Left: (2,1)=6, (2,0)=7, val = 8, bottom = 1.
    • Up: (1,0)=8, val = 9, left = 1.
    • Matrix = [[1,2,3],[8,0,4],[7,6,5]].
  • Step 2: Second layer.
    • top = 1, bottom = 1, left = 1, right = 1.
    • Right: (1,1)=9, val = 10, top = 2.
    • Matrix = [[1,2,3],[8,9,4],[7,6,5]].
  • Step 3: top > bottom, stop.
  • Finish: Return [[1,2,3],[8,9,4],[7,6,5]].

Example 2: n = 1

We need [[1]].

  • Start: n = 1, matrix = [[0]], val = 1.
  • Step 1: top = 0, bottom = 0, left = 0, right = 0.
    • Right: (0,0)=1, top = 1.
  • Finish: Return [[1]].

How the Code Works (Layer-by-Layer)

Here’s the Python code with line-by-line explanation:

def generateMatrix(n: int) -> list[list[int]]:
    # Line 1: Initialize matrix and variables
    matrix = [[0] * n for _ in range(n)]
    top, bottom = 0, n - 1
    left, right = 0, n - 1
    val = 1

    # Line 2: Fill layers
    while val <= n * n:
        # Line 3: Fill right
        for j in range(left, right + 1):
            matrix[top][j] = val
            val += 1
        top += 1

        # Line 4: Fill down
        for i in range(top, bottom + 1):
            matrix[i][right] = val
            val += 1
        right -= 1

        # Line 5: Fill left (if still valid)
        if top <= bottom:
            for j in range(right, left - 1, -1):
                matrix[bottom][j] = val
                val += 1
            bottom -= 1

        # Line 6: Fill up (if still valid)
        if left <= right:
            for i in range(bottom, top - 1, -1):
                matrix[i][left] = val
                val += 1
            left += 1

    # Line 7: Return completed matrix
    return matrix

Alternative: Direction Array Approach

Explanation

Use a direction array to define movement (right, down, left, up) and fill the matrix by changing direction when hitting a boundary or filled cell. Track the current position and value, continuing until (n^2) elements are placed.

  1. Initialize Matrix and Direction.
  2. Fill with Directions.
  • Move, place value, change direction if needed.

3. Return Matrix.

Step-by-Step Example (Alternative)

For (n = 3):

  • Start: matrix = [[0,0,0],[0,0,0],[0,0,0]], dir = [(0,1),(1,0),(0,-1),(-1,0)], i = 0, j = 0, d = 0, val = 1.
  • Step 1: Right: [1,2,3], i = 0, j = 2, d = 1, val = 4.
  • Step 2: Down: [4,5], i = 2, j = 2, d = 2, val = 6.
  • Step 3: Left: [6,7], i = 2, j = 0, d = 3, val = 8.
  • Step 4: Up: [8,9], i = 1, j = 0, done.
  • Finish: Matrix = [[1,2,3],[8,9,4],[7,6,5]], return it.

How the Code Works (Direction Array)

def generateMatrixDir(n: int) -> list[list[int]]:
    # Line 1: Initialize matrix and variables
    matrix = [[0] * n for _ in range(n)]
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # Right, down, left, up
    i, j = 0, 0
    d = 0  # Direction index
    val = 1

    # Line 2: Fill matrix
    while val <= n * n:
        # Line 3: Place current value
        matrix[i][j] = val
        val += 1

        # Line 4: Next position
        next_i, next_j = i + directions[d][0], j + directions[d][1]

        # Line 5: Change direction if needed
        if (next_i < 0 or next_i >= n or 
            next_j < 0 or next_j >= n or 
            matrix[next_i][next_j] != 0):
            d = (d + 1) % 4
            next_i, next_j = i + directions[d][0], j + directions[d][1]

        # Line 6: Move to next position
        i, j = next_i, next_j

    # Line 7: Return completed matrix
    return matrix

Complexity

  • Layer-by-Layer:
    • Time: O(n^2) – Fill each of \(n^2\) elements once.
    • Space: O(1) – Only boundaries (excluding output matrix).
  • Direction Array:
    • Time: O(n^2) – Fill each element once.
    • Space: O(1) – Only variables (excluding output).

Efficiency Notes

Both are O(n^2) time and O(1) space (excluding the output matrix), suitable for LeetCode 59. Layer-by-Layer is more structured and easier to follow, while Direction Array is flexible but requires careful boundary checking.

Key Insights

Tips to master LeetCode 59:

  • Layer Logic: Fill boundaries systematically.
  • Boundary Shrink: Move inward after each layer.
  • Spiral Pattern: Right, down, left, up sequence.

Additional Example

For (n = 2):

  • Goal: [[1,2],[4,3]].
  • Layer: Right [1,2], down [3], left [], up [4].
  • Result: [[1,2],[4,3]].

Edge Cases

  • \(n = 1\): [[1]].
  • \(n = 2\): [[1,2],[4,3]].
  • \(n = 20\): Fill 400 elements spirally.

Final Thoughts

The Layer-by-Layer Generation solution is a top choice for LeetCode 59 in Python—clean, efficient, and perfect for spiral creation. For a related challenge, try LeetCode 54: Spiral Matrix to traverse an existing matrix! Ready to spiral? Solve LeetCode 59 on LeetCode now and test it with (n = 3) or (n = 4) to master matrix generation. Dive in and spin it up!