Domain 2MediumCORE

Spiral Matrix

The goal is to traverse a 2D matrix in a clockwise spiral pattern, starting from the top-left corner and moving right. We need to return all elements as a single flattened list.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Array

54. Spiral Matrix

Model: qwen3.5:9b
Topics: Array
FAANG asked: 1
Acceptance rate: 36.5%


Problem Breakdown

The goal is to traverse a 2D matrix in a clockwise spiral pattern, starting from the top-left corner and moving right. We need to return all elements as a single flattened list.

Inputs: A rectangular m x n integer matrix (List[List[int]]). Outputs: A flat List[int]. Constraints & Edge Cases:

  • Dimensions are at least 1x1 (no empty matrices per constraints, but logic should handle it).
  • Values can be negative.
  • The tricky part is managing the boundaries so we don’t re-traverse rows or columns that have already been visited, especially when m equals n, or in single-row/column cases where top/bottom and left/right indices might overlap.

Intuition

A naive approach would try to simulate movement with a direction vector (Right -> Down -> Left -> Up) using coordinates (r, c) and changing directions upon hitting boundaries. While valid, this requires tracking visited cells or complex boundary conditions for each turn.

The stronger insight is Boundary Shrinkage. Instead of moving step-by-step through the grid, we treat the matrix as a shrinking rectangle defined by four indices: top, bottom, left, and right.

  1. Traverse from left to right along the top row, then increment top (consume that row).
  2. Traverse from top to bottom along the right column, then decrement right (consume that col).
  3. Check if boundaries crossed before traversing back: traverse right-to-left on the new bottom row, decrement bottom.
  4. Similarly check and traverse up the left side, increment left.

This ensures every element is visited exactly once in O(M×N)O(M \times N) time without extra space for a “visited” set.

Approach

  1. Initialize four boundary pointers: top = 0, bottom = m - 1, left = 0, right = n - 1.
  2. Use a while loop that continues as long as the boundaries haven’t crossed (top <= bottom and left <= right).
  3. Inside the loop:
    • Top Row: Iterate columns from left to right. Append elements, then increment top.
    • Right Column: Iterate rows from top to bottom. Append elements, decrement right.
    • Bottom Row (Conditional): If boundaries still valid (top <= bottom), iterate right-to-left. Decrement bottom. This check is crucial because if we just finished the top row and there was only one row left, incrementing top would make it cross bottom, so traversing again here would be redundant or wrong.
    • Left Column (Conditional): If boundaries still valid (left <= right), iterate bottom-to-top. Increment left.

Complexity Analysis

  • Time: O(m×n)O(m \times n). We visit every cell in the matrix exactly once during the traversal steps.
  • Space: O(1)O(1) auxiliary space (excluding the output list which is required to store the result). The boundary pointers use constant extra memory.

Solution

def spiralOrder(matrix):
    if not matrix: 
        return []
    
    m, n = len(matrix), len(matrix[0])
    top, bottom = 0, m - 1
    left, right = 0, n - 1
    
    result = []
    
    while top <= bottom and left <= right:
        # Traverse Top Row (Left -> Right)
        for col in range(left, right + 1):
            result.append(matrix[top][col])
        top += 1
        
        # Traverse Right Column (Top -> Bottom)
        if top > bottom: break 
        for row in range(top, bottom + 1):
            result.append(matrix[row][right])
        right -= 1
        
        # Traverse Bottom Row (Right -> Left)
        if left > right: break
        for col in range(right, left - 1, -1):
            result.append(matrix[bottom][col])
        bottom -= 1
        
        # Traverse Left Column (Bottom -> Top)
        if top > bottom: break
        for row in range(bottom, top - 1, -1):
            result.append(matrix[row][left])
        left += 1
            
    return result

Edge Cases Handled

  • Single Row Matrix: The top increment happens immediately after the first pass. Subsequent checks (if top > bottom) prevent traversing a non-existent right column or bottom row again, preventing duplicates.
  • Single Column Matrix: Similar logic applies; horizontal passes happen once (or zero times if width is 1), vertical passes handle the rest correctly via boundary decrements/increments.
  • Square Matrix (m=nm=n): The standard shrinking rectangle logic works perfectly without special casing for square vs rectangular grids.