Spiral Matrix

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

Spiral order means traversing the matrix starting from the top-left corner, going right across the top, then down the right side, then left across the bottom, then up the left side — and repeating inward until all elements are collected.

Examples

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

Prerequisites

Before attempting this problem, you should be comfortable with:

• 2D Array Indexing — accessing elements by row and column indices
• Boundary Tracking — maintaining and updating four pointers (top, bottom, left, right) to represent shrinking boundaries
• Direction Vectors — encoding directional movement as row/column delta pairs (dr, dc)
• Simulation — faithfully executing the described traversal pattern step by step

1. Recursion (DFS)

Intuition

Model the spiral as a recursive DFS that always moves in one direction until it either hits a boundary or a visited cell. When blocked, it rotates 90° clockwise and continues. The recursion terminates naturally when all cells have been visited.

Start at position (0, -1) — one step left of the top-left — facing right (0, 1). The first move steps into (0, 0) and the spiral unfolds from there.

Algorithm

• Initialize result = [], visited set, direction vectors [(0,1),(1,0),(0,-1),(-1,0)] (right, down, left, up), direction index d = 0.
• Call dfs(row=0, col=-1, r=0, c=1) to begin facing right just before column 0.
• In dfs: compute next (nr, nc) = (row+r, col+c).
• If (nr, nc) is in bounds and not visited, append matrix[nr][nc] to result, mark visited, recurse as dfs(nr, nc, r, c).
• Otherwise, rotate 90° clockwise: new direction (r, c) = (c, -r). Recurse as dfs(row, col, r, c).
• Stop if result length equals total cells.

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        rows, cols = len(matrix), len(matrix[0])
        result = []
        visited = set()

        def dfs(row, col, r, c):
            if len(result) == rows * cols:
                return
            nr, nc = row + r, col + c
            if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in visited:
                result.append(matrix[nr][nc])
                visited.add((nr, nc))
                dfs(nr, nc, r, c)
            else:
                # Rotate 90° clockwise: (r, c) → (c, -r)
                dfs(row, col, c, -r)

        dfs(0, -1, 0, 1)
        return result

class Solution {
    int rows, cols;
    boolean[][] visited;
    List<Integer> result = new ArrayList<>();
    int[][] matrix;

    public List<Integer> spiralOrder(int[][] matrix) {
        this.matrix = matrix;
        rows = matrix.length; cols = matrix[0].length;
        visited = new boolean[rows][cols];
        dfs(0, -1, 0, 1);
        return result;
    }

    void dfs(int row, int col, int r, int c) {
        if (result.size() == rows * cols) return;
        int nr = row + r, nc = col + c;
        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && !visited[nr][nc]) {
            result.add(matrix[nr][nc]);
            visited[nr][nc] = true;
            dfs(nr, nc, r, c);
        } else {
            dfs(row, col, c, -r); // rotate 90° clockwise
        }
    }
}

Time Complexity: O(m·n) — each cell visited once.
Space Complexity: O(m·n) — visited set + recursion stack up to m·n deep.

2. Iteration (Boundary Tracking)

Intuition

Maintain four boundary pointers — top, bottom, left, right — that shrink inward after each side is traversed. No visited set is needed; boundaries prevent revisiting. This is the most readable and commonly expected solution.

Algorithm

• Initialize top = 0, bottom = rows-1, left = 0, right = cols-1.
• While left ≤ right and top ≤ bottom:
• → Right: iterate c from left to right, append matrix[top][c]. Then top++.
• ↓ Down: iterate r from top to bottom, append matrix[r][right]. Then right--.
• ← Left: if top ≤ bottom, iterate c from right to left, append matrix[bottom][c]. Then bottom--.
• ↑ Up: if left ≤ right, iterate r from bottom to top, append matrix[r][left]. Then left++.

3. Iteration Optimal (Direction Vectors)

Intuition

Instead of four explicit boundary loops, encode direction as a pair (dr, dc) and track how many steps remain in the current direction. After every two direction changes, the step counts alternate between cols-decreasing and rows-decreasing. The key observation: steps[d & 1] tells how many cells to take in the current half-cycle. After each direction change, decrement the corresponding step count.

The four directions cycle as: right → down → left → up → right … encoded as dr = [0,1,0,-1], dc = [1,0,-1,0]. d & 1 extracts the LSB of direction index — 0 for horizontal, 1 for vertical — indexing into steps = [cols, rows-1].

Algorithm

• Initialize dr = [0,1,0,-1], dc = [1,0,-1,0], direction index d = 0.
• Set steps = [cols, rows-1]. Current position (r, c) = (0, 0). Append matrix[0][0].
• While steps[d & 1] > 0: take steps[d & 1] steps in direction d, appending each cell.
• After finishing direction d: decrement steps[d & 1]. Rotate direction: d = (d + 1) % 4.

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        rows, cols = len(matrix), len(matrix[0])
        dr = [0, 1, 0, -1]
        dc = [1, 0, -1, 0]
        steps = [cols, rows - 1]
        result = [matrix[0][0]]
        d, r, c = 0, 0, 0

        while steps[d & 1] > 0:
            for _ in range(steps[d & 1]):
                r += dr[d]
                c += dc[d]
                result.append(matrix[r][c])
            steps[d & 1] -= 1
            d = (d + 1) % 4

        return result

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        int rows = matrix.length, cols = matrix[0].length;
        int[] dr = {0, 1, 0, -1};
        int[] dc = {1, 0, -1, 0};
        int[] steps = {cols, rows - 1};
        List<Integer> result = new ArrayList<>();
        result.add(matrix[0][0]);
        int d = 0, r = 0, c = 0;

        while (steps[d & 1] > 0) {
            for (int i = 0; i < steps[d & 1]; i++) {
                r += dr[d]; c += dc[d];
                result.add(matrix[r][c]);
            }
            steps[d & 1]--;
            d = (d + 1) % 4;
        }
        return result;
    }
}

Time Complexity: O(m·n) — each cell visited exactly once.
Space Complexity: O(1) extra space (excluding the output list).

Common Pitfalls

Missing the Single-Row or Single-Column Guard

After traversing right across the top row (top++) and down the right column (right--), you must check top ≤ bottom before going left, and left ≤ right before going up. Without these guards, a single-row or single-column matrix will traverse that row/column twice — once going right, once going left — producing duplicates.

# Wrong — no guard:
for c in range(right, left - 1, -1):
    result.append(matrix[bottom][c])   # duplicates top row!

# Correct — guard first:
if top <= bottom:
    for c in range(right, left - 1, -1):
        result.append(matrix[bottom][c])

Off-by-One in Boundary Updates

Each boundary pointer must be updated immediately after its side is fully traversed. A common mistake is forgetting to update top after the right traversal, causing an infinite loop or revisiting the first row. Always increment/decrement boundaries right after the loop, not at the end of the outer while-loop body.

Wrong Starting Position in Recursive DFS

The DFS variant starts at (0, -1) facing right — not at (0, 0). Starting at (0, 0) and appending immediately skips the natural guard, requiring special-case code. The (0, -1) start lets the first recursive step naturally land at (0, 0) and enter the standard path.

Confusing d & 1 in the Optimal Approach

steps[d & 1] uses the least-significant bit of d to index into steps: direction 0 (right) and direction 2 (left) are both horizontal and share steps[0] = cols; directions 1 (down) and 3 (up) are vertical and share steps[1] = rows-1. After each direction completes, decrement steps[d & 1] before rotating — this is what causes the bounds to shrink.