Spiral Matrix

medium
Arrays & HashingArrayMatrix

Given an m x n matrix, return all elements of the matrix in spiral order. Spiral order starts from the top-left corner and proceeds right, then down, then left, then up, repeating this pattern and moving inward until all elements are visited.

Examples

Example 1

  • Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
  • Output: [1,2,3,6,9,8,7,4,5]
  • Explanation: Traverse right across the top row, down the right column, left across the bottom row, and up the left column, then continue inward.

Example 2

  • Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
  • Output: [1,2,3,4,8,12,11,10,9,5,6,7]

Constraints

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

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Simulation with Visited Matrix

Intuition

Simulate the spiral traversal by maintaining a visited matrix and a direction vector. Start moving right; when you hit a boundary or a visited cell, turn clockwise (right -> down -> left -> up). Continue until all cells are visited. This is an intuitive simulation approach that directly models the spiral movement.

Algorithm

  1. Create a visited matrix of the same dimensions, initialized to false.
  2. Define direction vectors for right, down, left, and up. Start with direction index 0 (right).
  3. Start at position (0, 0). Add the current element to the result and mark it as visited.
  4. Compute the next position. If it is out of bounds or already visited, change direction clockwise.
  5. Move to the next position and repeat until all m*n elements are collected.
TimeO(m * n)SpaceO(m * n)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        int dr[] = {0, 1, 0, -1};
        int dc[] = {1, 0, -1, 0};

        vector<int> result;
        int r = 0, c = 0, dir = 0;

        for (int i = 0; i < m * n; i++) {
            result.push_back(matrix[r][c]);
            visited[r][c] = true;

            int nr = r + dr[dir];
            int nc = c + dc[dir];

            if (nr < 0 || nr >= m || nc < 0 || nc >= n || visited[nr][nc]) {
                dir = (dir + 1) % 4;
                nr = r + dr[dir];
                nc = c + dc[dir];
            }

            r = nr;
            c = nc;
        }

        return result;
    }
};
Java 21
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean[][] visited = new boolean[m][n];
        int[] dr = {0, 1, 0, -1};
        int[] dc = {1, 0, -1, 0};

        List<Integer> result = new ArrayList<>();
        int r = 0, c = 0, dir = 0;

        for (int i = 0; i < m * n; i++) {
            result.add(matrix[r][c]);
            visited[r][c] = true;

            int nr = r + dr[dir];
            int nc = c + dc[dir];

            if (nr < 0 || nr >= m || nc < 0 || nc >= n || visited[nr][nc]) {
                dir = (dir + 1) % 4;
                nr = r + dr[dir];
                nc = c + dc[dir];
            }

            r = nr;
            c = nc;
        }

        return result;
    }
}
Python 3.12
def spiralOrder(matrix: list[list[int]]) -> list[int]:
    m, n = len(matrix), len(matrix[0])
    visited = [[False] * n for _ in range(m)]
    dr = [0, 1, 0, -1]
    dc = [1, 0, -1, 0]

    result = []
    r, c, d = 0, 0, 0

    for _ in range(m * n):
        result.append(matrix[r][c])
        visited[r][c] = True

        nr, nc = r + dr[d], c + dc[d]

        if nr < 0 or nr >= m or nc < 0 or nc >= n or visited[nr][nc]:
            d = (d + 1) % 4
            nr, nc = r + dr[d], c + dc[d]

        r, c = nr, nc

    return result
Go 1.26
func spiralOrder(matrix [][]int) []int {
    m, n := len(matrix), len(matrix[0])
    visited := make([][]bool, m)
    for i := range visited {
        visited[i] = make([]bool, n)
    }
    dr := []int{0, 1, 0, -1}
    dc := []int{1, 0, -1, 0}

    result := make([]int, 0, m*n)
    r, c, dir := 0, 0, 0

    for i := 0; i < m*n; i++ {
        result = append(result, matrix[r][c])
        visited[r][c] = true

        nr := r + dr[dir]
        nc := c + dc[dir]

        if nr < 0 || nr >= m || nc < 0 || nc >= n || visited[nr][nc] {
            dir = (dir + 1) % 4
            nr = r + dr[dir]
            nc = c + dc[dir]
        }

        r = nr
        c = nc
    }

    return result
}
Approach 2

Layer-by-Layer Peeling

Intuition

Instead of simulating step by step, process the matrix layer by layer from the outside in. Each layer is a rectangular ring. Use four boundary variables (top, bottom, left, right) that shrink inward after each side of the ring is traversed. For each layer, traverse right along the top row, down along the right column, left along the bottom row (if it exists), and up along the left column (if it exists).

Algorithm

  1. Initialize four boundaries: top = 0, bottom = m-1, left = 0, right = n-1.
  2. While top <= bottom and left <= right, traverse the current layer:
  3. Return the result.
TimeO(m * n)SpaceO(1)

Code (C++ · Java · Python · Go)

C++17
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 j = left; j <= right; j++) {
                result.push_back(matrix[top][j]);
            }
            top++;

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

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

            if (left <= right) {
                for (int i = bottom; i >= top; i--) {
                    result.push_back(matrix[i][left]);
                }
                left++;
            }
        }

        return result;
    }
};
Java 21
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 j = left; j <= right; j++) {
                result.add(matrix[top][j]);
            }
            top++;

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

            if (top <= bottom) {
                for (int j = right; j >= left; j--) {
                    result.add(matrix[bottom][j]);
                }
                bottom--;
            }

            if (left <= right) {
                for (int i = bottom; i >= top; i--) {
                    result.add(matrix[i][left]);
                }
                left++;
            }
        }

        return result;
    }
}
Python 3.12
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 j in range(left, right + 1):
            result.append(matrix[top][j])
        top += 1

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

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

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

    return result
Go 1.26
func spiralOrder(matrix [][]int) []int {
    result := []int{}
    top, bottom := 0, len(matrix)-1
    left, right := 0, len(matrix[0])-1

    for top <= bottom && left <= right {
        for j := left; j <= right; j++ {
            result = append(result, matrix[top][j])
        }
        top++

        for i := top; i <= bottom; i++ {
            result = append(result, matrix[i][right])
        }
        right--

        if top <= bottom {
            for j := right; j >= left; j-- {
                result = append(result, matrix[bottom][j])
            }
            bottom--
        }

        if left <= right {
            for i := bottom; i >= top; i-- {
                result = append(result, matrix[i][left])
            }
            left++
        }
    }

    return result
}

Frequently asked questions

What is the optimal time complexity of Spiral Matrix?

The most efficient approach in this guide ("Layer-by-Layer Peeling") runs in O(m * n) time and uses O(1) extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Spiral Matrix use?

Spiral Matrix is a medium-level Arrays & Hashing problem involving Array, Matrix. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Spiral Matrix be solved without extra space?

The most space-efficient approach in this guide uses O(1) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(m * n), while the optimized version uses O(1).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Related Problems

Set Matrix ZeroesRotate Image

Original problem: leetcode.com

Loading editor...
Input
matrix=
[[1,2,3],[4,5,6],[7,8,9]]
Expected Output
[1,2,3,6,9,8,7,4,5]