LeetCode 54: Spiral Matrix Solution in Python Explained

Problem Statement

LeetCode 54, Spiral Matrix, is a medium-level problem where you’re given an (m \times n) matrix of integers matrix. Your task is to return all elements of the matrix in spiral order—traversing clockwise from the top-left corner, spiraling inward through the layers until all elements are visited. The result should be a single list of integers.

Constraints

  • m == matrix.length: Number of rows.
  • n == matrix[i].length: Number of columns.
  • 1 <= m, n <= 10: Matrix dimensions are between 1 and 10.
  • -100 <= matrix[i][j] <= 100: Elements are within this range.

Example

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

Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]
Explanation: Spiral order for 3x4 matrix.

Input: matrix = [[7],[8],[9]]
Output: [7,8,9]
Explanation: Single column, top to bottom.

Understanding the Problem

How do you solve LeetCode 54: Spiral Matrix in Python? For matrix = [[1,2,3],[4,5,6],[7,8,9]], traverse in spiral order to get [1,2,3,6,9,8,7,4,5]. We need to visit each element exactly once, moving right, down, left, up, and shrinking the boundaries inward. We’ll explore two approaches: a Layer-by-Layer Traversal Solution (optimal and primary) and an Alternative with Direction Array (intuitive but more complex). The layer-by-layer method processes the matrix in O(m * n) time with O(1) extra space.

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

Explanation

Traverse the matrix layer by layer, maintaining four boundaries: top, bottom, left, and right. For each layer, visit elements rightward, downward, leftward, and upward, then shrink the boundaries inward. Stop when all elements are visited (i.e., when boundaries cross).

Here’s a flow for [[1,2,3],[4,5,6],[7,8,9]]:

Layer 1: 1→2→3→6→9→8→7
Layer 2: 4→5
Result: [1,2,3,6,9,8,7,4,5]
  1. Initialize Boundaries.
  • Top = 0, bottom = m-1, left = 0, right = n-1.
  1. Traverse Layers.
  • Right, down, left, up, adjust boundaries.
  1. Check Termination.
  • Stop when top > bottom or left > right.
  1. Return Result.

Step-by-Step Example

Example 1: matrix = [[1,2,3],[4,5,6],[7,8,9]]

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

  • Goal: Traverse in spiral order.
  • Result for Reference: [1,2,3,6,9,8,7,4,5].
  • Start: matrix = [[1,2,3],[4,5,6],[7,8,9]], m = 3, n = 3, result = [], top = 0, bottom = 2, left = 0, right = 2.
  • Step 1: First layer.
    • Right: (0,0)=1, (0,1)=2, (0,2)=3, result = [1,2,3], top += 1 (1).
    • Down: (1,2)=6, (2,2)=9, result = [1,2,3,6,9], right -= 1 (1).
    • Left: (2,1)=8, (2,0)=7, result = [1,2,3,6,9,8,7], bottom -= 1 (1).
    • Up: (1,0)=4, result = [1,2,3,6,9,8,7,4], left += 1 (1).
  • Step 2: Second layer.
    • top = 1, bottom = 1, left = 1, right = 1.
    • Right: (1,1)=5, result = [1,2,3,6,9,8,7,4,5], top += 1 (2).
    • top > bottom, stop.
  • Finish: Return [1,2,3,6,9,8,7,4,5].

Example 2: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]

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

  • Start: m = 3, n = 4, top = 0, bottom = 2, left = 0, right = 3.
  • Step 1: First layer.
    • Right: [1,2,3,4], top = 1.
    • Down: [8,12], right = 2.
    • Left: [11,10,9], bottom = 1.
    • Up: [5], left = 1.
    • Result = [1,2,3,4,8,12,11,10,9,5].
  • Step 2: Second layer.
    • Right: [6,7], top = 2.
    • Result = [1,2,3,4,8,12,11,10,9,5,6,7].
  • Finish: Return [1,2,3,4,8,12,11,10,9,5,6,7].

How the Code Works (Layer-by-Layer)

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

def spiralOrder(matrix: list[list[int]]) -> list[int]:
    # Line 1: Handle edge case
    if not matrix:
        return []

    # Line 2: Initialize boundaries and result
    m, n = len(matrix), len(matrix[0])
    result = []
    top, bottom = 0, m - 1
    left, right = 0, n - 1

    # Line 3: Traverse layers
    while top <= bottom and left <= right:
        # Line 4: Traverse right
        for j in range(left, right + 1):
            result.append(matrix[top][j])
        top += 1

        # Line 5: Traverse down
        for i in range(top, bottom + 1):
            result.append(matrix[i][right])
        right -= 1

        if top <= bottom:
            # Line 6: Traverse left
            for j in range(right, left - 1, -1):
                result.append(matrix[bottom][j])
            bottom -= 1

        if left <= right:
            # Line 7: Traverse up
            for i in range(bottom, top - 1, -1):
                result.append(matrix[i][left])
            left += 1

    # Line 8: Return spiral order
    return result

Alternative: Direction Array Approach

Explanation

Use a direction array to define movement (right, down, left, up) and track visited cells with a set or by checking boundaries. Change direction when hitting a boundary or visited cell, continuing until all elements are visited.

  1. Initialize Direction and Visited.
  2. Traverse with Directions.
  • Move, append, change direction if needed.

3. Return Result.

Step-by-Step Example (Alternative)

For [[1,2,3],[4,5,6],[7,8,9]]:

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

How the Code Works (Direction Array)

def spiralOrderDir(matrix: list[list[int]]) -> list[int]:
    # Line 1: Handle edge case
    if not matrix:
        return []

    # Line 2: Initialize variables
    m, n = len(matrix), len(matrix[0])
    result = []
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # Right, down, left, up
    i, j = 0, 0
    d = 0  # Direction index
    seen = set()

    # Line 3: Traverse until all visited
    while len(result) < m * n:
        # Line 4: Add current element
        result.append(matrix[i][j])
        seen.add((i, j))

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

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

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

    # Line 8: Return spiral order
    return result

Complexity

  • Layer-by-Layer:
    • Time: O(m * n) – Visit each element once.
    • Space: O(1) – Only boundaries and result list.
  • Direction Array:
    • Time: O(m * n) – Visit each element once.
    • Space: O(m * n) – Visited set.

Efficiency Notes

Layer-by-Layer is O(m * n) time and O(1) space (excluding output), optimal for LeetCode 54. Direction Array is also O(m * n) time but uses O(m * n) space for tracking, less space-efficient but flexible.

Key Insights

Tips to master LeetCode 54:

  • Boundary Control: Shrink layers systematically.
  • Four Steps: Right, down, left, up in order.
  • Edge Checking: Prevent overstepping boundaries.

Additional Example

For matrix = [[1,2],[3,4]]:

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

Edge Cases

  • 1x1: [[1]] – Return [1].
  • 1xn: [[1,2,3]] – Return [1,2,3].
  • mx1: [[1],[2]] – Return [1,2].

Final Thoughts

The Layer-by-Layer Traversal solution is a perfect fit for LeetCode 54 in Python—clean, efficient, and space-saving. For a related challenge, try LeetCode 53: Maximum Subarray to switch gears with arrays! Ready to spiral? Solve LeetCode 54 on LeetCode now and test it with [[1,2,3],[4,5,6]] or a 4x4 grid to master spiral traversal. Dive in and twist through it!