54. Spiral Matrix

Spiral Matrix looks like a drawing exercise, but the whole thing turns on bookkeeping: which cells have you already visited, and where does the next turn happen? Track four edges instead of a visited grid and the code almost writes itself. It sits in the matrix and geometry pattern, where the recurring move is walking a grid by shrinking its bounds.

The problem

Given an m x n grid of numbers, read every cell once in clockwise spiral order — start top-left, go right across the top, down the right side, left along the bottom, up the left side, then inward — and return that flat list. (Full statement on LeetCode.)

A tiny case makes the order concrete. For

1 2 3
4 5 6
7 8 9

the spiral is 1 2 3 6 9 8 7 4 5: the outer ring first, then the lone center.

Intuition: four edges that close in

The naive instinct is to mark each cell as visited and turn whenever the next step would run off the grid or hit a used cell. That works, but it costs an extra $O(mn)$ grid and a fiddly direction-change rule.

There’s a cleaner mental model. A spiral is just concentric rectangular rings, and every ring is bounded by four numbers: top, bottom, left, right. Walk one full lap — right along top, down right, left along bottom, up left — and after each edge is consumed, move that boundary one step inward. When the boundaries cross (top > bottom or left > right), every cell is spent and you stop. No visited set, no direction vector: the four variables are the state.

The one subtlety is a thin leftover. When the remaining region is a single row or single column, the top edge and bottom edge (or left and right) refer to the same line. After the rightward and downward passes shrink the box, that last strip can get walked twice. Guarding the leftward and upward passes with a fresh top <= bottom / left <= right check is what keeps a 1 x n or n x 1 tail from double-counting.

Solution

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

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> order = new ArrayList<>();
        int top = 0, bottom = matrix.length - 1;
        int left = 0, right = matrix[0].length - 1;

        while (top <= bottom && left <= right) {
            // Top edge: left -> right, then retire this row
            for (int c = left; c <= right; c++) order.add(matrix[top][c]);
            top++;

            // Right edge: top -> bottom, then retire this column
            for (int r = top; r <= bottom; r++) order.add(matrix[r][right]);
            right--;

            // Bottom edge: right -> left. Skip if the last row was already taken.
            if (top <= bottom) {
                for (int c = right; c >= left; c--) order.add(matrix[bottom][c]);
                bottom--;
            }

            // Left edge: bottom -> top. Skip if the last column was already taken.
            if (left <= right) {
                for (int r = bottom; r >= top; r--) order.add(matrix[r][left]);
                left++;
            }
        }
        return order;
    }
}

Each cell is added exactly once, and the loop ends the moment the two boundaries pass each other. The two inner if guards are the only defensive lines, and they exist purely for the single-row and single-column tail described above.

Complexity

	Time	Space
Boundary shrinking	$O(m \cdot n)$	$O(1)$

Every cell is read once, so time is $O(mn)$. Beyond the output list, the only memory is four integers — $O(1)$ auxiliary space, versus the $O(mn)$ a visited grid would cost.

In an interview

Say the ring model out loud before writing anything: “I’ll track four boundaries and peel one edge off after each pass, so I never need a visited array.” That framing signals you’ve seen the structure, not just memorized a traversal. Then write the four loops in order and let the boundaries update between them.

The trap they’ll probe is the thin case. Feed your own code a 1 x 4 row or a 4 x 1 column in your head — without the if (top <= bottom) and if (left <= right) guards, the bottom and left passes re-read cells the first two passes already took. Naming why those guards are there, rather than adding them by reflex, is the tell that you actually reasoned through it.

This edge-tracking move is the backbone of the matrix and geometry pattern. It pairs naturally with Rotate Image, which also manipulates a grid by layers, and with Set Matrix Zeroes, where the trick is likewise to avoid an extra $O(mn)$ marker array.

References

• LeetCode 54 — Spiral Matrix