Spiral Matrix

Q: What is the best time complexity for Spiral Matrix?

Optimal (shrinking boundaries) runs in O(m · n) time and O(1) extra space. Each cell is read exactly once.

Q: Which pattern does Spiral Matrix use?

It is a arrays & hashing problem that uses the matrix traversal pattern.

Q: Is there a brute force solution for Spiral Matrix?

Yes. Brute force (simulate with a visited grid) takes O(m · n) time and O(m · n) space. Walk like a robot: start at the top-left heading right, and turn clockwise whenever the next cell is outside the matrix or already visited.

Q: Which edge cases should I test for Spiral Matrix?

A single row or a single column; A 1 x 1 matrix; Wide or tall rectangles where the last layer is one row or one column, which must not be read twice.

Medium Arrays & Hashing Matrix Traversal Original on LeetCode

Reported atMicrosoft Adobe

Spiral Matrix is a medium arrays & hashing problem solved with the matrix traversal pattern. The best approach, optimal (shrinking boundaries), runs in O(m · n) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (simulate with a visited grid) up.

Problem

Given an m x n integer matrix, return all of its elements in spiral order: start at the top-left corner, move right along the first row, then down the last column, left along the last row, up the first column, and keep circling inward clockwise until every element has been listed once.

Examples

Example 1

Input: matrix = [[10, 11, 12, 13], [20, 21, 22, 23], [30, 31, 32, 33]]
Output: [10, 11, 12, 13, 23, 33, 32, 31, 30, 20, 21, 22]
Why: Go right along the top row, down the right column, left along the bottom row, up the left column, then the remaining inner row 21, 22.

Example 2

Input: matrix = [[3, 8, 1], [6, 2, 7]]
Output: [3, 8, 1, 7, 2, 6]
Why: After the outer ring there is nothing left inside.

Example 3

Input: matrix = [[5], [9], [4]]
Output: [5, 9, 4]
Why: A single column is read straight down.

Constraints

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

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00

Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

Approach	Time	Space
Brute force (simulate with a visited grid)	`O(m · n)`	`O(m · n)`
Optimal (shrinking boundaries)	`O(m · n)`	`O(1)`

1Brute force (simulate with a visited grid)

TimeO(m · n)Every cell is visited once with constant work.

SpaceO(m · n)The visited grid has one flag per cell.

Walk like a robot: start at the top-left heading right, and turn clockwise whenever the next cell is outside the matrix or already visited. A separate boolean grid remembers visited cells.

Directions in order: right, down, left, up.
Repeat m * n times: record the cell, mark it visited, compute the next cell.
If the next cell is out of range or visited, turn to the next direction and recompute.

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean[][] seen = new boolean[m][n];
        int[] dr = { 0, 1, 0, -1 }, dc = { 1, 0, -1, 0 };
        List<Integer> res = new ArrayList<>();
        int r = 0, c = 0, d = 0;
        for (int k = 0; k < m * n; k++) {
            res.add(matrix[r][c]);
            seen[r][c] = true;
            int nr = r + dr[d], nc = c + dc[d];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n || seen[nr][nc]) {
                d = (d + 1) % 4;
                nr = r + dr[d];
                nc = c + dc[d];
            }
            r = nr;
            c = nc;
        }
        return res;
    }
}

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        m, n = len(matrix), len(matrix[0])
        seen = [[False] * n for _ in range(m)]
        dr, dc = [0, 1, 0, -1], [1, 0, -1, 0]
        res = []
        r = c = d = 0
        for _ in range(m * n):
            res.append(matrix[r][c])
            seen[r][c] = True
            nr, nc = r + dr[d], c + dc[d]
            if nr < 0 or nr >= m or nc < 0 or nc >= n or seen[nr][nc]:
                d = (d + 1) % 4
                nr, nc = r + dr[d], c + dc[d]
            r, c = nr, nc
        return res

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<bool>> seen(m, vector<bool>(n, false));
        int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0};
        vector<int> res;
        int r = 0, c = 0, d = 0;
        for (int k = 0; k < m * n; k++) {
            res.push_back(matrix[r][c]);
            seen[r][c] = true;
            int nr = r + dr[d], nc = c + dc[d];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n || seen[nr][nc]) {
                d = (d + 1) % 4;
                nr = r + dr[d];
                nc = c + dc[d];
            }
            r = nr;
            c = nc;
        }
        return res;
    }
};

function spiralOrder(matrix) {
    const m = matrix.length, n = matrix[0].length;
    const seen = Array.from({ length: m }, () => new Array(n).fill(false));
    const dr = [0, 1, 0, -1], dc = [1, 0, -1, 0];
    const res = [];
    let r = 0, c = 0, d = 0;
    for (let k = 0; k < m * n; k++) {
        res.push(matrix[r][c]);
        seen[r][c] = true;
        let nr = r + dr[d], nc = c + dc[d];
        if (nr < 0 || nr >= m || nc < 0 || nc >= n || seen[nr][nc]) {
            d = (d + 1) % 4;
            nr = r + dr[d];
            nc = c + dc[d];
        }
        r = nr;
        c = nc;
    }
    return res;
}

2Optimal (shrinking boundaries)

TimeO(m · n)Each cell is read exactly once.

SpaceO(1)Four integers besides the output list.

Track the unread rectangle with four boundaries. Read its top row, right column, bottom row and left column in that order, pulling each boundary inward after its side is read. Guard the bottom row and left column so a single leftover row or column is not read twice.

top = 0, bottom = m - 1, left = 0, right = n - 1.
While top <= bottom and left <= right: read top row left to right, then top++.
Read right column top to bottom, then right--.
If top <= bottom: read bottom row right to left, then bottom--.
If left <= right: read left column bottom to top, then left++.

class Solution {
    public 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;
    }
}

class Solution:
    def spiralOrder(self, 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:
            for c in range(left, right + 1):
                res.append(matrix[top][c])
            top += 1
            for r in range(top, bottom + 1):
                res.append(matrix[r][right])
            right -= 1
            if top <= bottom:
                for c in range(right, left - 1, -1):
                    res.append(matrix[bottom][c])
                bottom -= 1
            if left <= right:
                for r in range(bottom, top - 1, -1):
                    res.append(matrix[r][left])
                left += 1
        return res

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> res;
        int top = 0, bottom = matrix.size() - 1, left = 0, right = 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;
    }
};

function spiralOrder(matrix) {
    const res = [];
    let top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1;
    while (top <= bottom && left <= right) {
        for (let c = left; c <= right; c++) res.push(matrix[top][c]);
        top++;
        for (let r = top; r <= bottom; r++) res.push(matrix[r][right]);
        right--;
        if (top <= bottom) {
            for (let c = right; c >= left; c--) res.push(matrix[bottom][c]);
            bottom--;
        }
        if (left <= right) {
            for (let r = bottom; r >= top; r--) res.push(matrix[r][left]);
            left++;
        }
    }
    return res;
}

Edge cases to test

A single row or a single column
A 1 x 1 matrix
Wide or tall rectangles where the last layer is one row or one column, which must not be read twice

Hints

Hint 1

Think of the matrix as nested rings. Each ring is read top row, right column, bottom row, left column.

Hint 2

Keep four boundaries: top, bottom, left, right. After reading a side, move that boundary inward.

Hint 3

Before reading the bottom row or the left column, check that the boundaries have not crossed, or a lone middle row or column gets read twice.

FAQ

What is the best time complexity for Spiral Matrix?

Optimal (shrinking boundaries) runs in O(m · n) time and O(1) extra space. Each cell is read exactly once.

Which pattern does Spiral Matrix use?

It is a arrays & hashing problem that uses the matrix traversal pattern.

Is there a brute force solution for Spiral Matrix?

Yes. Brute force (simulate with a visited grid) takes O(m · n) time and O(m · n) space. Walk like a robot: start at the top-left heading right, and turn clockwise whenever the next cell is outside the matrix or already visited.

Which edge cases should I test for Spiral Matrix?

A single row or a single column; A 1 x 1 matrix; Wide or tall rectangles where the last layer is one row or one column, which must not be read twice.