Spiral Matrix

Problem

Given an m x n matrix, return all elements of the matrix in spiral order.

Example 1:

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

Example 2:

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]

Constraints:

m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrix[i][j] <= 100

Solution

Approach 1: Layer by Layer

The key insight is to traverse the matrix in concentric rectangular layers, moving from outermost to innermost.

Implementation

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix:
            return []

        result = []
        top, bottom = 0, len(matrix) - 1
        left, right = 0, len(matrix[0]) - 1

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

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

            # Traverse left (if still have rows)
            if top <= bottom:
                for col in range(right, left - 1, -1):
                    result.append(matrix[bottom][col])
                bottom -= 1

            # Traverse up (if still have columns)
            if left <= right:
                for row in range(bottom, top - 1, -1):
                    result.append(matrix[row][left])
                left += 1

        return result

Approach 2: Direction Vectors

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix:
            return []

        m, n = len(matrix), len(matrix[0])
        result = []
        seen = [[False] * n for _ in range(m)]

        # Directions: right, down, left, up
        dr = [0, 1, 0, -1]
        dc = [1, 0, -1, 0]

        r = c = di = 0

        for _ in range(m * n):
            result.append(matrix[r][c])
            seen[r][c] = True

            # Try to move in current direction
            nr, nc = r + dr[di], c + dc[di]

            # Change direction if needed
            if 0 <= nr < m and 0 <= nc < n and not seen[nr][nc]:
                r, c = nr, nc
            else:
                # Turn clockwise
                di = (di + 1) % 4
                r, c = r + dr[di], c + dc[di]

        return result

Approach 3: Recursive

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        def spiral(top, bottom, left, right):
            if top > bottom or left > right:
                return []

            result = []

            # Top row
            for col in range(left, right + 1):
                result.append(matrix[top][col])

            # Right column
            for row in range(top + 1, bottom + 1):
                result.append(matrix[row][right])

            # Bottom row (if exists)
            if top < bottom:
                for col in range(right - 1, left - 1, -1):
                    result.append(matrix[bottom][col])

            # Left column (if exists)
            if left < right:
                for row in range(bottom - 1, top, -1):
                    result.append(matrix[row][left])

            # Recurse on inner layer
            return result + spiral(top + 1, bottom - 1, left + 1, right - 1)

        if not matrix:
            return []
        return spiral(0, len(matrix) - 1, 0, len(matrix[0]) - 1)

Complexity Analysis

Time Complexity: O(m × n), where m and n are the dimensions. We visit each element exactly once.
Space Complexity: O(1) for iterative approach (not counting output array), O(min(m, n)) for recursive approach due to call stack.

Key Insights

Boundary Management: Track four boundaries (top, bottom, left, right) that shrink inward after each edge traversal.
Direction Pattern: Movement follows right → down → left → up pattern, repeating in layers.
Edge Cases: Handle single row or single column matrices correctly by checking boundaries before traversing.
Complete Traversal: Continue until boundaries cross (top > bottom or left > right).
Four Steps per Layer: Each complete layer involves four edge traversals with boundary updates.
Visited Tracking: Alternative approach uses seen array to track visited cells and change direction when blocked.
Rectangle Peeling: Think of it as peeling off the outer rectangle layer by layer until nothing remains.