LeetCode Spiral Matrix: Boundary Walk Pattern

Spiral Matrix (LeetCode 54, Medium) tests one thing: can you keep four moving boundaries straight without an off-by-one? Yes, if you write the template once and trust it.

The Problem

Given an m x n matrix, return all elements of the matrix in spiral order, starting at the top-left and going clockwise.

Example:

• Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
• Output: [1,2,3,6,9,8,7,4,5]

Brute Force

Mark visited cells in a parallel matrix and follow direction vectors.

def spiral_brute(matrix):
    if not matrix:
        return []
    m, n = len(matrix), len(matrix[0])
    visited = [[False] * n for _ in range(m)]
    dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    r = c = d = 0
    result = []
    for _ in range(m * n):
        result.append(matrix[r][c])
        visited[r][c] = True
        nr, nc = r + dirs[d][0], c + dirs[d][1]
        if not (0 <= nr < m and 0 <= nc < n) or visited[nr][nc]:
            d = (d + 1) % 4
            nr, nc = r + dirs[d][0], c + dirs[d][1]
        r, c = nr, nc
    return result

Correct, but uses O(m*n) extra space.

Optimal Solution

Maintain four shrinking boundaries: top, bottom, left, right. Walk one edge at a time and contract.

def spiral_order(matrix):
    if not matrix:
        return []
    result = []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    while top <= bottom and left <= right:
        for c in range(left, right + 1):
            result.append(matrix[top][c])
        top += 1
        for r in range(top, bottom + 1):
            result.append(matrix[r][right])
        right -= 1
        if top <= bottom:
            for c in range(right, left - 1, -1):
                result.append(matrix[bottom][c])
            bottom -= 1
        if left <= right:
            for r in range(bottom, top - 1, -1):
                result.append(matrix[r][left])
            left += 1
    return result

O(m*n) time, O(1) extra space beyond the output.

Walk Through an Example

matrix = [[1,2,3],[4,5,6],[7,8,9]]. Bounds: top=0, bottom=2, left=0, right=2.

• Top row: append 1, 2, 3. top=1.
• Right column: append 6, 9. right=1.
• Bottom row right-to-left: append 8, 7. bottom=1.
• Left column bottom-to-top: append 4. left=1.

Now top=1, bottom=1, left=1, right=1.

• Top row: append 5. top=2.
• Right column: nothing (top > bottom). Loop exits at next iteration.

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

Edge Cases

• Empty matrix or empty first row: return [].
• Single row: the first inner loop appends everything; the second appends nothing because top > bottom after the increment.
• Single column: symmetric to the single-row case.
• Non-square matrix like 2x4 or 4x2: the guards if top <= bottom and if left <= right prevent the final leg from double-counting cells.

Complexity Analysis

• Time: O(m*n). Every cell is visited exactly once.
• Space: O(1) extra beyond the output list.

The boundary approach beats the visited-matrix brute force in space and keeps the logic flat.

How to Explain It in an Interview

Draw the four-boundary picture. Say: “Each layer is four edges. I’ll walk them in order and shrink the corresponding boundary.” Emphasize the two guards before the third and fourth edges; they handle the rectangular cases. Walk through a 3x3 once and a 2x4 once to demonstrate that the guards matter. Avoid the visited-matrix solution unless asked, but mention it as an alternative.

Related Problems

• LeetCode 59 Spiral Matrix II (construct the spiral)
• LeetCode 48 Rotate Image (transpose + reverse)
• LeetCode 885 Spiral Matrix III (start from arbitrary cell)
• LeetCode 498 Diagonal Traverse

Wrap up

Spiral Matrix rewards a clean template and disciplined boundary updates. Write the four-boundary version a couple of times and the guards become muscle memory. Pair it with Rotate Image and [Set Matrix Zeroes] in a matrix-manipulation study block to lock in 2D index gymnastics.