Spiral Matrix

Problem Description

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

Examples

Constraints

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

Navigating Four-Way Boundaries Inward

To traverse a matrix spirally, we must move in four directions in a cyclic pattern: right, down, left, up.

Instead of writing complex path equations, we can track the active boundaries of the grid:

• top (starts at 0)
• bottom (starts at m - 1)
• left (starts at 0)
• right (starts at n - 1)

At each step, we run four consecutive traversals:

1. Traverse from left to right along the top row. Then increment top.
2. Traverse from top to bottom along the right column. Then decrement right.
3. Traverse from right to left along the bottom row (only if top <= bottom). Then decrement bottom.
4. Traverse from bottom to top along the left column (only if left <= right). Then increment left.

We repeat this loop until the boundaries cross (left > right or top > bottom).

Solution 1: Boundary Shrinking Traversal (Optimal)

Track four boundary pointers, shrinking them inward as rows and columns are fully traversed.

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        if (matrix == null || matrix.length == 0) return result;

        int top = 0;
        int bottom = matrix.length - 1;
        int left = 0;
        int right = matrix[0].length - 1;

        while (left <= right && top <= bottom) {
            // Traverse Right
            for (int c = left; c <= right; c++) {
                result.add(matrix[top][c]);
            }
            top++;

            // Traverse Down
            for (int r = top; r <= bottom; r++) {
                result.add(matrix[r][right]);
            }
            right--;

            // Traverse Left (guard against duplicate traversal of same row)
            if (top <= bottom) {
                for (int c = right; c >= left; c--) {
                    result.add(matrix[bottom][c]);
                }
                bottom--;
            }

            // Traverse Up (guard against duplicate traversal of same col)
            if (left <= right) {
                for (int r = bottom; r >= top; r--) {
                    result.add(matrix[r][left]);
                }
                left++;
            }
        }
        return result;
    }
}

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

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

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

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

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

            # Traverse Up
            if left <= right:
                for r in range(bottom, top - 1, -1):
                    result.append(matrix[r][left])
                left += 1

        return result

#include <vector>

class Solution {
public:
    std::vector<int> spiralOrder(std::vector<std::vector<int>>& matrix) {
        std::vector<int> result;
        if (matrix.empty()) return result;

        int top = 0;
        int bottom = (int)matrix.size() - 1;
        int left = 0;
        int right = (int)matrix[0].size() - 1;

        while (left <= right && top <= bottom) {
            // Traverse Right
            for (int c = left; c <= right; c++) {
                result.push_back(matrix[top][c]);
            }
            top++;

            // Traverse Down
            for (int r = top; r <= bottom; r++) {
                result.push_back(matrix[r][right]);
            }
            right--;

            // Traverse Left
            if (top <= bottom) {
                for (int c = right; c >= left; c--) {
                    result.push_back(matrix[bottom][c]);
                }
                bottom--;
            }

            // Traverse Up
            if (left <= right) {
                for (int r = bottom; r >= top; r--) {
                    result.push_back(matrix[r][left]);
                }
                left++;
            }
        }
        return result;
    }
};

Complexity Analysis:

• Time Complexity: O(m * n) where m is the number of rows and n is the number of columns. We visit every element in the matrix exactly once.
• Space Complexity: O(1) auxiliary space (excluding the output array).

Where it breaks: If you forget to check top <= bottom before traversing left, or left <= right before traversing up, the code will duplicate rows/columns on thin rectangular matrices (like a single row [[1,2,3]] or a single column).

Common Mistakes

• Omitting the inner top <= bottom and left <= right guards. On rectangular matrices (e.g., a single-row matrix [[1, 2, 3]]), the top++ operation will cause top > bottom. Without the guard, the traverse-left loop will run anyway, reading the same row in reverse.
• Off-by-one errors in reverse loop indices. When iterating backward in C++ or Python, ensure the range boundaries go all the way down to left and top, inclusive.
• Modifying boundaries inside loop scopes. Boundaries must only change after completing the full pass along that boundary line.

Frequently Asked Questions

How does this handle a single-row or single-column matrix? The inner loop guards prevent duplicate reads. For a single row [[1, 2, 3]], the traverse-right loop runs. top is incremented. The traverse-down loop does not run because top > bottom. The traverse-left and traverse-up guards also evaluate to false, ending the traversal safely.

Can we solve this using direction offsets and a visited set? Yes. You can use a direction cycle array dr = [0, 1, 0, -1], dc = [1, 0, -1, 0], and change direction whenever you hit the grid boundary or a visited cell. However, this requires O(m * n) space for the visited set, which is less optimal than the boundary pointers.

What does this problem test in interviews? It tests your ability to coordinate indices, handle uneven rectangular matrices, and write loops with strict boundaries.

← All Problems