Spiral Traverse

Category

Arrays

Difficulty

Medium

Problem Statement

Given a two-dimensional array (matrix), return all of its elements in spiral order. Spiral order starts at the top-left corner, moves right across the top row, then down the right column, then left across the bottom row, then up the left column, and continues inward repeating this pattern.

Intuition

We can define four boundaries — top, bottom, left, right — that shrink inward as we complete each layer of the spiral. By iterating along each boundary in the correct direction and then contracting that boundary, we systematically visit every element exactly once.

Approach

1. Initialize top = 0, bottom = rows - 1, left = 0, right = cols - 1.
2. Initialize an empty result list.
3. While top <= bottom and left <= right:
   • Traverse from left to right along top row; increment top.
   • Traverse from top to bottom along right column; decrement right.
   • If top <= bottom, traverse from right to left along bottom row; decrement bottom.
   • If left <= right, traverse from bottom to top along left column; increment left.
4. Return the result list.

Pseudocode

function spiralTraverse(matrix):
    result = []
    top = 0
    bottom = rows(matrix) - 1
    left = 0
    right = cols(matrix) - 1

    while top <= bottom and left <= right:
        for col from left to right:
            result.append(matrix[top][col])
        top += 1

        for row from top to bottom:
            result.append(matrix[row][right])
        right -= 1

        if top <= bottom:
            for col from right down to left:
                result.append(matrix[bottom][col])
            bottom -= 1

        if left <= right:
            for row from bottom down to top:
                result.append(matrix[row][left])
            left += 1

    return result

Time & Space Complexity

• Time: O(n) where n is the total number of elements in the matrix — each element is visited exactly once.
• Space: O(n) for the result array. The algorithm itself uses O(1) auxiliary space.

Key Insights

• The inner boundary checks (if top <= bottom, if left <= right) prevent double-counting elements when the remaining area collapses to a single row or single column.
• This iterative approach avoids recursion overhead and is straightforward to implement.
• The same logic works for non-square matrices.

Edge Cases

• Empty matrix: return an empty list.
• Single row matrix: return the row as-is.
• Single column matrix: return the column as-is.
• 1x1 matrix: return the single element.
• Non-square matrix (e.g., 3x5): the boundary checks handle the asymmetry.