137.Spiral Matrix

MediumBlind 75Math & Geometry · 2/8

Problem

Given an m x n matrix, return all of its elements in spiral order: start at the top-left, go right along the top row, down the right column, left along the bottom row, up the left column, and keep spiralling inward until every element has been visited.

Examples

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

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

💡 Key Insight

The spiral is a sequence of shrinking rectangle boundaries. Keep four walls — top, bottom, left, right — and after walking each side, move that wall inward by one. The only subtlety is non-square matrices: after the top row and right column, the remaining rectangle may already be empty, so check top <= bottom and left <= right before walking the bottom row and left column.

Simulation with Visited Array

TimeO(m · n)SpaceO(m · n)

Intuition

Simulate a walker. It moves in direction order right → down → left → up. When the next cell is outside the matrix or already visited, it turns clockwise. After m · n steps every cell has been collected.

Algorithm

dr = {0, 1, 0, -1}, dc = {1, 0, -1, 0}; start at (0, 0), direction 0.
Repeat m · n times:
- Add matrix[r][c], mark visited.
- Compute the next cell; if it is invalid or visited, turn: d = (d + 1) % 4.
- Move to the next cell in direction d.

Visualization

1 → 2 → 3
        ↓
4 → 5   6      the walker turns at the wall (3), at the wall (9),
↑       ↓      at the wall (7), and at the visited cell (1),
7 ← 8 ← 9      then at visited 6 after reaching 5.

output: 1 2 3 6 9 8 7 4 5

Code

java

import java.util.*;

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[] dr = {0, 1, 0, -1}; // right, down, left, up
        int[] dc = {1, 0, -1, 0};
        boolean[][] visited = new boolean[m][n];
        List<Integer> result = new ArrayList<>();
        int r = 0, c = 0, d = 0;
        for (int step = 0; step < m * n; step++) {
            result.add(matrix[r][c]);
            visited[r][c] = true;
            int nr = r + dr[d], nc = c + dc[d];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n || visited[nr][nc]) {
                d = (d + 1) % 4; // blocked: turn clockwise
                nr = r + dr[d];
                nc = c + dc[d];
            }
            r = nr;
            c = nc;
        }
        return result;
    }
}

Complexity

Time: O(m · n) — one step per cell.
Space: O(m · n) — the visited array.

Layer-by-Layer BoundariesOptimal

TimeO(m · n)SpaceO(1)

Intuition

Instead of remembering every visited cell, remember only the four walls of the unvisited rectangle. Walk the top row and push top down; walk the right column and pull right in; then — only if rows remain — walk the bottom row backwards and lift bottom; and — only if columns remain — walk the left column upward and push left in.

Algorithm

top = 0, bottom = m - 1, left = 0, right = n - 1.
While top <= bottom && left <= right:
- For c in left..right: add matrix[top][c]; then top++.
- For r in top..bottom: add matrix[r][right]; then right--.
- If top <= bottom: for c in right..left (descending): add matrix[bottom][c]; bottom--.
- If left <= right: for r in bottom..top (descending): add matrix[r][left]; left++.

Visualization

flowchart TD
    A["T=0 B=2 L=0 R=3<br/>top row → 1 2 3 4"] --> B1["T=1<br/>right col ↓ 8 12"]
    B1 --> C["R=2<br/>bottom row ← 11 10 9"]
    C --> D["B=1<br/>left col ↑ 5"]
    D --> E["L=1 T=1 B=1 R=2<br/>top row → 6 7"]
    E --> F["T=2 > B=1<br/>skip bottom and stop"]

Code

java

import java.util.*;

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 c = left; c <= right; c++) result.add(matrix[top][c]);     // →
            top++;
            for (int r = top; r <= bottom; r++) result.add(matrix[r][right]);   // ↓
            right--;
            if (top <= bottom) { // a row is still left to walk backwards
                for (int c = right; c >= left; c--) result.add(matrix[bottom][c]); // ←
                bottom--;
            }
            if (left <= right) { // a column is still left to walk upwards
                for (int r = bottom; r >= top; r--) result.add(matrix[r][left]);   // ↑
                left++;
            }
        }
        return result;
    }
}

Complexity

Time: O(m · n) — every element is added exactly once.
Space: O(1) — only four indices (output excluded).

Complexity Comparison

Approach	Time	Space (extra)
Simulation + visited	O(m · n)	O(m · n)
Boundaries	O(m · n)	O(1)

Common Pitfalls

Omitting the top <= bottom / left <= right checks — a single remaining row (e.g. [[1,2,3]]) gets read twice, forward and backward.
Updating a wall before its loop instead of after it, shifting the walked row/column by one.
Assuming the matrix is square — test 1 x n, m x 1 and 3 x 4 shapes.
In the simulation, turning only on out-of-bounds and forgetting the visited check — the walker re-enters the outer ring.