Spiral Matrix

mediumAmazon-tagged: Arrays & Strings49 stepsJava · Python · C++

Read a matrix in clockwise spiral order. Keep four boundaries (top, bottom, left, right). Read the top row left to right, the right column top to bottom, the bottom row right to left, the left column bottom to top, shrinking each boundary after use.

▶ Watch the animated trace

Traced input: matrix = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]] → [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]. Original problem: neetcode.io/problems/spiral-matrix

Complexity

BestO(m·n)

AverageO(m·n)

WorstO(m·n)

SpaceO(1)

Each cell is read once; output not counted.

Key idea

Each pass peels one layer side by side.
Shrink the boundary right after reading its side.
Check top <= bottom and left <= right before the bottom row and left column, or a single row/column is read twice.

Common mistakes

Missing the mid-loop checks duplicates the middle row or column.
Using a visited array works but costs O(m·n) space.

Solution

Java

List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> res = new ArrayList<>();
    int top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1;
    while (top <= bottom && left <= right) {
        for (int c = left; c <= right; c++) res.add(matrix[top][c]);
        top++;
        for (int r = top; r <= bottom; r++) res.add(matrix[r][right]);
        right--;
        if (top <= bottom) {
            for (int c = right; c >= left; c--) res.add(matrix[bottom][c]);
            bottom--;
        }
        if (left <= right) {
            for (int r = bottom; r >= top; r--) res.add(matrix[r][left]);
            left++;
        }
    }
    return res;
}

Python

def spiralOrder(matrix: List[List[int]]) -> List[int]:
    res = []
    top, bottom, left, right = 0, len(matrix) - 1, 0, len(matrix[0]) - 1
    while top <= bottom and left <= right:
        res += [matrix[top][c] for c in range(left, right + 1)]
        top += 1
        res += [matrix[r][right] for r in range(top, bottom + 1)]
        right -= 1
        if top <= bottom:
            res += [matrix[bottom][c] for c in range(right, left - 1, -1)]
            bottom -= 1
        if left <= right:
            res += [matrix[r][left] for r in range(bottom, top - 1, -1)]
            left += 1
    return res

C++

vector<int> spiralOrder(vector<vector<int>>& matrix) {
    vector<int> res;
    int top = 0, bottom = (int)matrix.size() - 1, left = 0, right = (int)matrix[0].size() - 1;
    while (top <= bottom && left <= right) {
        for (int c = left; c <= right; c++) res.push_back(matrix[top][c]);
        top++;
        for (int r = top; r <= bottom; r++) res.push_back(matrix[r][right]);
        right--;
        if (top <= bottom) {
            for (int c = right; c >= left; c--) res.push_back(matrix[bottom][c]);
            bottom--;
        }
        if (left <= right) {
            for (int r = bottom; r >= top; r--) res.push_back(matrix[r][left]);
            left++;
        }
    }
    return res;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Single row The bottom-row pass is skipped.	`matrix = [[1, 2, 3]]`	`[1, 2, 3]`
Single column The left-column pass is skipped.	`matrix = [[1], [2], [3]]`	`[1, 2, 3]`
Square One full layer.	`matrix = [[1, 2], [3, 4]]`	`[1, 2, 4, 3]`