Free lesson · DSA Mastery - Interview Prep, End to End

Spiral Matrix

Medium7 min readdsamatrix

Spiral Matrix

Spiral Matrix is the canonical 2D-traversal problem: given an m × n grid, return all its elements in spiral order - rightward across the top row, down the right column, leftward across the bottom, up the left, then inward and repeat. There's no clever asymptotic trick here; the entire challenge is controlling four moving boundaries without revisiting or skipping a cell. We present the standard boundary-shrinking approach, which is the clean, bug-resistant way every strong candidate writes it, alongside a direction-vector variant that some find easier to reason about.

The skill this trains is boundary discipline - the same careful index bookkeeping that underlies every matrix-traversal and transformation problem in this module.

The Problem

Interactive animation: Nine numbers read ring by ring: walk right, turn at every wall, and move that wall in.

Given an m x n matrix, return all elements of the matrix in spiral order.

Example 1:

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

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 Overview

#	Approach	Time	Space	Verdict
1	Four-boundary shrinking	O(m·n)	O(1) extra	Standard & clearest
2	Direction vectors + visited tracking	O(m·n)	O(m·n)	Intuitive alternative

Every cell is visited exactly once, so O(m·n) time is optimal - you must touch each element to output it. The only real question is how cleanly you manage the spiral path. (Output array space isn't counted as extra.)

Approach 1: Four-Boundary Shrinking - Standard

The Idea

Interactive animation: The cells still unread always form a rectangle, so four numbers replace a whole visited grid.

Maintain four boundaries: top, bottom, left, right. Repeatedly walk the four edges of the current rectangle - left-to-right along top, top-to-bottom along right, right-to-left along bottom, bottom-to-top along left - and after each edge, shrink that boundary inward. Stop when the boundaries cross. The guards before the bottom and left passes prevent double-counting the middle row/column in non-square matrices.

Logic Flowchart

graph TD
    A["top=0, bottom=m-1<br/>left=0, right=n-1"] --> B{"top <= bottom AND left <= right?"}
    B -->|No| C["Done"]
    B -->|Yes| D["walk top row left→right; top++"]
    D --> E["walk right col top→bottom; right--"]
    E --> F{"top <= bottom?"}
    F -->|Yes| G["walk bottom row right→left; bottom--"]
    F -->|No| H["skip"]
    G --> I{"left <= right?"}
    H --> I
    I -->|Yes| J["walk left col bottom→top; left++"]
    I -->|No| K["skip"]
    J --> B
    K --> B

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style G fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style H fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style I fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style J fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style K fill:#4338ca,stroke:#6366f1,color:#f1f5f9

This flowchart shows the four-boundary approach. We keep top, bottom, left, and right boundaries. Each loop walks the top row rightward then shrinks top, the right column downward then shrinks right, the bottom row leftward if rows remain then shrinks bottom, and the left column upward if columns remain then shrinks left. We stop when the boundaries cross.

Code

public static 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 row →
        top++;
        for (int r = top; r <= bottom; r++) result.add(matrix[r][right]); // right col ↓
        right--;
        if (top <= bottom) {                                              // bottom row ←
            for (int c = right; c >= left; c--) result.add(matrix[bottom][c]);
            bottom--;
        }
        if (left <= right) {                                              // left col ↑
            for (int r = bottom; r >= top; r--) result.add(matrix[r][left]);
            left++;
        }
    }
    return result;
}

// Usage:
// spiralOrder(new int[][]{{1,2,3},{4,5,6},{7,8,9}}) -> [1,2,3,6,9,8,7,4,5]

This Java code keeps four boundaries and walks the top row rightward, the right column downward, the bottom row leftward, and the left column upward, shrinking each boundary after its pass. Guards before the bottom and left passes prevent re-visiting the middle row or column. It stops when the boundaries cross.

Step-by-Step Walkthrough

Interactive animation: Step through both approaches on the lesson's grids, including the 3 x 4 rectangle and a single column.

A frame-by-frame trace on the 3×3 matrix [[1,2,3],[4,5,6],[7,8,9]]. Each frame shows one edge pass and the boundary shrink:

graph LR
    F0["top row →<br/>1,2,3; top=1"]
    F1["right col ↓<br/>6,9; right=1"]
    F2["bottom row ←<br/>8,7; bottom=1"]
    F3["left col ↑<br/>4; left=1"]
    F4["top row →<br/>5; done"]
    F0 --> F1 --> F2 --> F3 --> F4

    style F0 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F1 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F2 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F4 fill:#4338ca,stroke:#6366f1,color:#f1f5f9

This walkthrough spirals the three by three matrix. The top row gives one, two, three. The right column gives six, nine. The bottom row gives eight, seven. The left column gives four. Finally the lone center cell gives five. The order is one, two, three, six, nine, eight, seven, four, five.

Result: [1,2,3,6,9,8,7,4,5].

Complexity

Time: O(m·n) - each cell visited once. Space: O(1) extra (excluding the output list).

Approach 2: Direction Vectors + Visited Tracking

Interactive animation: Walk and turn: the seen grid on the right fills up until it is as big as the matrix itself.

The Idea

Walk one step at a time using a direction vector that cycles right → down → left → up. Mark visited cells (or mutate them to a sentinel). Turn clockwise whenever the next step would go out of bounds or onto a visited cell. Conceptually simple - "keep walking, turn when blocked" - but needs O(m·n) space for the visited grid (unless you're allowed to mutate the matrix).

Logic Flowchart

graph TD
    A["dirs = [(0,1),(1,0),(0,-1),(-1,0)]<br/>r=0,c=0,d=0, visited grid"] --> B["For step = 1 to m*n"]
    B --> C["record matrix[r][c]; mark visited"]
    C --> D["compute next cell in dir d"]
    D --> E{"next out of bounds or visited?"}
    E -->|Yes| F["d = (d+1) % 4 (turn clockwise)"]
    E -->|No| G["keep d"]
    F --> H["advance r,c by dir d"]
    G --> H
    H --> I{"More steps?"}
    I -->|Yes| B
    I -->|No| J["Return result"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style E fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style F fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style G fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style H fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style I fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style J fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the direction-vector approach. We walk one cell at a time in the current direction, recording and marking each cell. When the next step would leave the grid or hit a visited cell, we turn clockwise. After m times n steps, every cell is recorded.

Code

public static List<Integer> spiralOrderDirs(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    boolean[][] seen = new boolean[m][n];
    int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};   // right, down, left, up
    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]);
        seen[r][c] = true;
        int nr = r + dirs[d][0], nc = c + dirs[d][1];
        if (nr < 0 || nr >= m || nc < 0 || nc >= n || seen[nr][nc]) {
            d = (d + 1) % 4;                              // turn clockwise
            nr = r + dirs[d][0];
            nc = c + dirs[d][1];
        }
        r = nr; c = nc;
    }
    return result;
}

This Java code walks one cell at a time using a cycling direction vector, recording and marking each cell. When the next step would leave the grid or revisit a cell, it turns clockwise. It needs a visited grid of the matrix's size.

Complexity

Time: O(m·n). Space: O(m·n) for the visited grid.

Complexity Comparison

Approach	Time	Space	Key Idea	When to Use
Four-boundary shrinking	O(m·n)	O(1)	Walk + shrink four edges	Standard, O(1) space
Direction vectors + visited	O(m·n)	O(m·n)	Turn clockwise when blocked	When boundary logic feels error-prone

Both are O(m·n) time (optimal - every cell must be output). The boundary approach wins on space and is the expected answer; the direction-vector version trades space for arguably simpler "walk and turn" logic.

Interactive animation: Both approaches on Example 1: the same nine reads, but only the walk and turn needs a second grid.

Variations & Follow-ups

How do you avoid double-counting in non-square matrices?

Interactive animation: On the 3 x 4 grid top passes bottom after 6, 7, so the guard skips the bottom row and 6 is not read twice.

The two guards (if (top <= bottom) before the bottom pass, if (left <= right) before the left pass) prevent re-walking a row or column that the earlier passes already consumed when the rectangle collapses to a single row or column.

What if you needed to fill a matrix in spiral order instead?

That's the next topic, Spiral Matrix II - same boundary walk, but writing values 1..n² instead of reading.

Can you do the direction-vector version without a visited grid?

Yes, if allowed to mutate the matrix - mark visited cells with a sentinel value outside the input range. Otherwise the boundary approach is the O(1)-space choice.

What about edge cases?

Single row: Just the top pass.
Single column: Top pass (one cell) then right pass down.
1×1: One element.
Wide vs. tall: The guards handle both; non-square is the main correctness risk.

Common Interview Pitfalls

Omitting the bottom/left guards. Causes double-counting the middle row/column in non-square matrices.
Shrinking a boundary before walking it. Walk the edge first, then shrink.
Off-by-one in the edge loops. Use inclusive bounds (<=, >=) consistently.
Assuming square input. m and n differ; never reuse one dimension for both.

Why This Problem Matters

Spiral Matrix is the archetype of boundary-controlled 2D traversal. The four-pointer discipline - walk an edge, shrink, guard against collapse - recurs across matrix problems and is exactly the kind of careful index management interviewers probe. There's no shortcut; correctness is the skill.

The next topic, Spiral Matrix II, is the mirror image: instead of reading a matrix in spiral order, you write 1 through n² into an n × n grid following the same spiral path - the identical boundary walk, repurposed for construction.

Back to DSA Mastery - Interview Prep, End to End