Spiral Matrix

medium Mixed Practice

Given an m x n matrix, return all elements of the matrix in spiral order. Spiral order means traversing the matrix starting from the top-left corner, moving right across the top row, then down the right column, then left across the bottom row, then up the left column, and repeating inward.

Example

Matrix:
[1, 2, 3]
[4, 5, 6]
[7, 8, 9]

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

Reading the matrix in spiral order means: go right along the top row (1, 2, 3), then down the right column (6, 9), then left along the bottom row (8, 7), then up the left column (4), and finally the center element (5).

Use four boundaries — top, bottom, left, right — to define the unvisited region. Traverse right along the top row, then down the right column, then left along the bottom row, then up the left column. After each pass, shrink the corresponding boundary inward. Stop when boundaries cross.

Why this works

Instead of tracking visited cells, you maintain four boundaries that define the unvisited rectangle. Each spiral pass peels off one layer: right across the top, down the right side, left across the bottom, up the left side. After each direction, the corresponding boundary shrinks inward. The boundary checks prevent double-counting rows or columns in non-square matrices.

Step by step

Initialize four boundaries — top, bottom, left, right define the current unvisited rectangle.
Traverse in four directions — right along top row, down along right column, left along bottom row, up along left column.
Shrink after each pass — move the boundary inward (e.g., top++ after traversing the top row).
Guard against single row/column — the if top <= bottom and if left <= right checks prevent re-traversing when the remaining region is a single row or column.

Time: O(m×n) Space: O(1)

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        int top = 0, bottom = matrix.length - 1;
        int left = 0, right = matrix[0].length - 1;
        while (top <= bottom && left <= right) {
            for (int col = left; col <= right; col++) // traverse top row →
                result.add(matrix[top][col]);
            top++; // shrink top boundary inward
            for (int row = top; row <= bottom; row++) // traverse right column ↓
                result.add(matrix[row][right]);
            right--;
            if (top <= bottom) {
                for (int col = right; col >= left; col--) // traverse bottom row ←
                    result.add(matrix[bottom][col]);
                bottom--;
            }
            if (left <= right) {
                for (int row = bottom; row >= top; row--) // traverse left column ↑
                    result.add(matrix[row][left]);
                left++;
            }
        }
        return result;
    }
}

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> result;
        int top = 0, bottom = matrix.size() - 1;
        int left = 0, right = matrix[0].size() - 1;
        while (top <= bottom && left <= right) {
            for (int col = left; col <= right; col++) // traverse top row →
                result.push_back(matrix[top][col]);
            top++; // shrink top boundary inward
            for (int row = top; row <= bottom; row++) // traverse right column ↓
                result.push_back(matrix[row][right]);
            right--;
            if (top <= bottom) {
                for (int col = right; col >= left; col--) // traverse bottom row ←
                    result.push_back(matrix[bottom][col]);
                bottom--;
            }
            if (left <= right) {
                for (int row = bottom; row >= top; row--) // traverse left column ↑
                    result.push_back(matrix[row][left]);
                left++;
            }
        }
        return result;
    }
};

def spiralOrder(matrix: list[list[int]]) -> list[int]:
    result = []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    while top <= bottom and left <= right:
        for col in range(left, right + 1):  # traverse top row →
            result.append(matrix[top][col])
        top += 1  # shrink top boundary inward
        for row in range(top, bottom + 1):  # traverse right column ↓
            result.append(matrix[row][right])
        right -= 1  # shrink right boundary inward
        if top <= bottom:
            for col in range(right, left - 1, -1):  # traverse bottom row ←
                result.append(matrix[bottom][col])
            bottom -= 1
        if left <= right:
            for row in range(bottom, top - 1, -1):  # traverse left column ↑
                result.append(matrix[row][left])
            left += 1
    return result