Spiral Matrix (LC 54): Shrinking Boundaries

Spiral Matrix (LeetCode 54): return all elements of an m x n matrix in clockwise spiral order. Simulate with a visited grid, or walk four shrinking boundaries for O(m*n) time and O(1) extra space.

Language Selection

Choose your preferred programming language

Showing: Python

Spiral Matrix

Problem Statement

Given an m x n matrix, return a list of all its elements in clockwise spiral order. Start at the top-left cell, move right along the top row, down the right column, left along the bottom row, up the left column, and keep spiralling inward until every cell has been visited exactly once.

Examples

Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9],[10,11,12]]
Output: [1,2,3,6,9,12,11,10,7,4,5,8]
Explanation: The outer ring gives 1,2,3,6,9,12,11,10,7,4; the inner column 5,8 comes last.

Example 2:

Input: matrix = [[7,-1,4,0]]
Output: [7,-1,4,0]
Explanation: A single row is read left to right.

Example 3:

Input: matrix = [[3,1],[8,6],[2,9]]
Output: [3,1,6,9,2,8]
Explanation: Right along the top (3,1), down the right column (6,9), left along the bottom (2),
then up the left column (8).

Constraints

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

Approach 1: Simulation with a Visited Grid

Algorithm

Walk the matrix the way a person would: keep a current position and a direction (right, down, left, up). Before each step, check whether the next cell is outside the matrix or already visited. If it is, turn clockwise. A separate boolean grid remembers visited cells.

Create a seen grid of size m x n, all false.
Direction vectors in clockwise order: right (0,1), down (1,0), left (0,-1), up (-1,0). Start at (0,0) facing right.
Repeat m * n times:
- Append the current cell to the result and mark it seen.
- Compute the next cell in the current direction. If it is out of bounds or seen, turn clockwise and recompute.
- Move to the next cell.
Return the result.

After the last cell the computed “next” position may be invalid, but the loop ends before it is used.

Implementation

Python:

from typing import List


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 = [0, 1, 0, -1]  # right, down, left, up
        dc = [1, 0, -1, 0]
        r = c = d = 0
        result = []
        for _ in range(m * n):
            result.append(matrix[r][c])
            seen[r][c] = True
            nr, nc = r + dr[d], c + dc[d]
            # Turn clockwise at a wall or an already visited cell
            if not (0 <= nr < m and 0 <= nc < n) or seen[nr][nc]:
                d = (d + 1) % 4
                nr, nc = r + dr[d], c + dc[d]
            r, c = nr, nc
        return result

Java:

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

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}; // right, down, left, up
        int[] dc = {1, 0, -1, 0};
        int r = 0, c = 0, d = 0;
        List<Integer> result = new ArrayList<>(m * n);
        for (int k = 0; k < m * n; k++) {
            result.add(matrix[r][c]);
            seen[r][c] = true;
            int nr = r + dr[d], nc = c + dc[d];
            // Turn clockwise at a wall or an already visited cell
            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 result;
    }
}

Go:

func spiralOrder(matrix [][]int) []int {
    m, n := len(matrix), len(matrix[0])
    seen := make([][]bool, m)
    for i := range seen {
        seen[i] = make([]bool, n)
    }
    dr := [4]int{0, 1, 0, -1} // right, down, left, up
    dc := [4]int{1, 0, -1, 0}
    r, c, d := 0, 0, 0
    result := make([]int, 0, m*n)
    for k := 0; k < m*n; k++ {
        result = append(result, matrix[r][c])
        seen[r][c] = true
        nr, nc := r+dr[d], c+dc[d]
        // Turn clockwise at a wall or an already visited cell
        if nr < 0 || nr >= m || nc < 0 || nc >= n || seen[nr][nc] {
            d = (d + 1) % 4
            nr, nc = r+dr[d], c+dc[d]
        }
        r, c = nr, nc
    }
    return result
}

JavaScript:

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]; // right, down, left, up
    const dc = [1, 0, -1, 0];
    let r = 0, c = 0, d = 0;
    const result = [];
    for (let k = 0; k < m * n; k++) {
        result.push(matrix[r][c]);
        seen[r][c] = true;
        let nr = r + dr[d], nc = c + dc[d];
        // Turn clockwise at a wall or an already visited cell
        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 result;
}

C#:

using System.Collections.Generic;

public class Solution {
    public IList<int> SpiralOrder(int[][] matrix) {
        int m = matrix.Length, n = matrix[0].Length;
        bool[,] seen = new bool[m, n];
        int[] dr = {0, 1, 0, -1}; // right, down, left, up
        int[] dc = {1, 0, -1, 0};
        int r = 0, c = 0, d = 0;
        var result = new List<int>(m * n);
        for (int k = 0; k < m * n; k++) {
            result.Add(matrix[r][c]);
            seen[r, c] = true;
            int nr = r + dr[d], nc = c + dc[d];
            // Turn clockwise at a wall or an already visited cell
            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 result;
    }
}

C++:

#include <vector>
using namespace std;

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));
        const int dr[4] = {0, 1, 0, -1}; // right, down, left, up
        const int dc[4] = {1, 0, -1, 0};
        int r = 0, c = 0, d = 0;
        vector<int> result;
        result.reserve(m * n);
        for (int k = 0; k < m * n; k++) {
            result.push_back(matrix[r][c]);
            seen[r][c] = true;
            int nr = r + dr[d], nc = c + dc[d];
            // Turn clockwise at a wall or an already visited cell
            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 result;
    }
};

Complexity Analysis

Time: O(m * n): each cell is visited once with O(1) work.
Space: O(m * n) for the seen grid, in addition to the output list.

Approach 2: Shrinking Boundaries (Optimal)

Algorithm

Instead of remembering every visited cell, keep four boundaries for the part of the matrix that has not been read yet: top, bottom, left, right. Each lap reads one full ring and pulls the boundaries inward.

Set top = 0, bottom = m - 1, left = 0, right = n - 1.
While top <= bottom and left <= right:
- Read row top from left to right, then top++.
- Read column right from top to bottom, then right--.
- If top <= bottom: read row bottom from right down to left, then bottom--.
- If left <= right: read column left from bottom up to top, then left++.
Return the result.

The two if checks matter when the remaining area is a single row or a single column. Without them the bottom row or left column would be read a second time, going backwards.

Implementation

Python:

from typing import List


class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        top, bottom = 0, len(matrix) - 1
        left, right = 0, len(matrix[0]) - 1
        result = []
        while top <= bottom and left <= right:
            for c in range(left, right + 1):  # top row, left -> right
                result.append(matrix[top][c])
            top += 1
            for r in range(top, bottom + 1):  # right column, top -> bottom
                result.append(matrix[r][right])
            right -= 1
            if top <= bottom:  # bottom row still unread
                for c in range(right, left - 1, -1):
                    result.append(matrix[bottom][c])
                bottom -= 1
            if left <= right:  # left column still unread
                for r in range(bottom, top - 1, -1):
                    result.append(matrix[r][left])
                left += 1
        return result

Java:

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

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        int top = 0, bottom = matrix.length - 1;
        int left = 0, right = matrix[0].length - 1;
        List<Integer> result = new ArrayList<>();
        while (top <= bottom && left <= right) {
            for (int c = left; c <= right; c++) result.add(matrix[top][c]);    // top row
            top++;
            for (int r = top; r <= bottom; r++) result.add(matrix[r][right]);  // right column
            right--;
            if (top <= bottom) { // bottom row still unread
                for (int c = right; c >= left; c--) result.add(matrix[bottom][c]);
                bottom--;
            }
            if (left <= right) { // left column still unread
                for (int r = bottom; r >= top; r--) result.add(matrix[r][left]);
                left++;
            }
        }
        return result;
    }
}

Go:

func spiralOrder(matrix [][]int) []int {
    top, bottom := 0, len(matrix)-1
    left, right := 0, len(matrix[0])-1
    result := make([]int, 0, len(matrix)*len(matrix[0]))
    for top <= bottom && left <= right {
        for c := left; c <= right; c++ { // top row
            result = append(result, matrix[top][c])
        }
        top++
        for r := top; r <= bottom; r++ { // right column
            result = append(result, matrix[r][right])
        }
        right--
        if top <= bottom { // bottom row still unread
            for c := right; c >= left; c-- {
                result = append(result, matrix[bottom][c])
            }
            bottom--
        }
        if left <= right { // left column still unread
            for r := bottom; r >= top; r-- {
                result = append(result, matrix[r][left])
            }
            left++
        }
    }
    return result
}

JavaScript:

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

C#:

using System.Collections.Generic;

public class Solution {
    public IList<int> SpiralOrder(int[][] matrix) {
        int top = 0, bottom = matrix.Length - 1;
        int left = 0, right = matrix[0].Length - 1;
        var result = new List<int>();
        while (top <= bottom && left <= right) {
            for (int c = left; c <= right; c++) result.Add(matrix[top][c]);    // top row
            top++;
            for (int r = top; r <= bottom; r++) result.Add(matrix[r][right]);  // right column
            right--;
            if (top <= bottom) { // bottom row still unread
                for (int c = right; c >= left; c--) result.Add(matrix[bottom][c]);
                bottom--;
            }
            if (left <= right) { // left column still unread
                for (int r = bottom; r >= top; r--) result.Add(matrix[r][left]);
                left++;
            }
        }
        return result;
    }
}

C++:

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int top = 0, bottom = (int)matrix.size() - 1;
        int left = 0, right = (int)matrix[0].size() - 1;
        vector<int> result;
        while (top <= bottom && left <= right) {
            for (int c = left; c <= right; c++) result.push_back(matrix[top][c]);    // top row
            top++;
            for (int r = top; r <= bottom; r++) result.push_back(matrix[r][right]);  // right column
            right--;
            if (top <= bottom) { // bottom row still unread
                for (int c = right; c >= left; c--) result.push_back(matrix[bottom][c]);
                bottom--;
            }
            if (left <= right) { // left column still unread
                for (int r = bottom; r >= top; r--) result.push_back(matrix[r][left]);
                left++;
            }
        }
        return result;
    }
};

Complexity Analysis

Time: O(m * n): every cell is appended exactly once.
Space: O(1) extra: four integer boundaries. The output list of size m * n is required by the problem and not counted.

Key Insights

The spiral is a sequence of rings. Each ring is four straight runs: top row, right column, bottom row, left column.
Boundaries replace the visited grid. Everything outside [top..bottom] x [left..right] has already been read, so four integers carry the same information as an m x n boolean grid.
Odd shapes end with a single row or column. The two guard checks stop the last row or column from being read twice.
Direction vectors generalise. The simulation approach adapts easily to other walks (counter-clockwise, starting elsewhere), which is why it is worth knowing too.

Edge Cases

Single cell: [[5]] returns [5].
Single row: [[7,-1,4,0]] returns [7,-1,4,0].
Single column: [[1],[2],[3]] returns [1,2,3].
Wide matrix: [[1,2,3,4],[5,6,7,8]] returns [1,2,3,4,8,7,6,5].
Tall matrix with a leftover middle column: [[1,2,3],[4,5,6],[7,8,9],[10,11,12]] returns [1,2,3,6,9,12,11,10,7,4,5,8].

Common Mistakes

Missing the guard checks. On [[1,2,3]] an unguarded loop outputs [1,2,3,2,1] or similar, reading the row back again.
Off-by-one on the boundaries. Update top before reading the right column, and right before reading the bottom row, or corner cells get read twice.
Assuming a square matrix. Use m and n separately; LeetCode’s tests include wide and tall shapes.
Looping until top < bottom. Using a strict inequality skips the last row or column in odd-sized matrices.
Mutating the input to mark visited cells with a sentinel value. It works only if you know a value that cannot appear, and it destroys the caller’s data.

Interview Tips

Draw the four boundaries on the example and shrink them by hand once before writing code.
Name your variables top, bottom, left, right. Single letters make the off-by-one bugs much harder to spot when reviewing your own code.
Test a single row and a single column right after coding. Those are the cases the guards exist for, and interviewers check them.
Mention the simulation approach as the alternative and explain the O(m * n) memory it costs.

Follow-up Questions

Spiral Matrix II (LC 59): fill an n x n matrix with 1..n² in spiral order. Same boundaries, writing instead of reading.
Counter-clockwise order: swap the order of the four runs (left column down first, then bottom row, and so on).
Spiral Matrix III (LC 885): walk a spiral outward from a given cell on a grid, including steps outside it; the run lengths follow the pattern 1, 1, 2, 2, 3, 3, …
Rotate Image (LC 48): the same ring-by-ring view lets you rotate a square matrix in place.
Return the k-th element of the spiral without building the full list: skip whole rings by their perimeter, then walk the final ring.

Language Selection

Spiral Matrix

Problem Statement

Examples

Constraints

Approach 1: Simulation with a Visited Grid

Algorithm

Implementation

Complexity Analysis

Approach 2: Shrinking Boundaries (Optimal)

Algorithm

Implementation

Complexity Analysis

Key Insights

Edge Cases

Common Mistakes

Interview Tips

Follow-up Questions

Related Problems

Share this