Pattern 1: Layer-by-layer traversal (spiral)

Traversing a matrix in a spiral seems to require logic full of exceptions. The secret is not to think cell by cell, but in terms of four bounds that enclose the not-yet-visited part and shrink with each edge traversed.

🎯

Try it first: Spiral Matrix

Before reading the theory, try to solve it. You can start with brute force, you can fail — the point is to feel the problem. The theory comes right below.

Given an m × n matrix, return all of its elements in spiral order (clockwise, starting from the top-left corner).

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

Carregando editor…

Tried it? Without a structure, it turns into a tangle of ifs and directions. The theory below organizes everything with four bound variables.

The theory: four shrinking bounds

Picture four walls enclosing the unvisited region: top, bottom, left, right. The spiral is always the same sequence of four moves, and after each one you push the corresponding wall inward:

1. top:     left → right    on row `top`        →  top++
2. right:   top → bottom    on column `right`   →  right--
3. bottom:  right → left    on row `bottom`     →  bottom--
4. left:    bottom → top    on column `left`    →  left++
repeat while top <= bottom and left <= right

The two extra checks (before the bottom and the left edges) cover non-square matrices, where a "loop" can finish in the middle. Watch the bounds shrink and the current cell follow the spiral — the light region is what is still left to visit:

Execução real, gravada passo a passo

Carregando Python no navegador (primeira vez demora alguns segundos)…

Why is it O(m·n) and O(1) (extra) space?

Each cell is visited exactly once along the spiral — that's m × n cells, so O(m·n) time. Apart from the output list (which is the answer, not counted as extra), we use only four bound integers → O(1) extra space. There is no way to be faster: you have to look at each cell at least once to list it.

The big idea: "layer by layer"

The spiral is a case of the layer-by-layer (or "shell by shell") strategy: solve the outer ring, shrink to the inner ring, repeat. The same idea reappears in rotating the image (next lesson, where you rotate ring by ring) and in several matrix problems. When a grid problem "wraps the edges and funnels inward", think of shrinking bounds.

A common interview variation is the inverse: generate a matrix in a spiral (fill 1..n² in spiral order) instead of reading. It is the same bound control — only writing instead of collecting. (It shows up in the final exam!)

🧠 Review quiz

0/4

1. What is the core idea of the spiral traversal?

2. Why check 'if top <= bottom' before traversing the bottom (and 'if left <= right' before the left)?

3. What is the complexity of the spiral traversal of an m×n matrix?

4. The 'shrinking bounds' / 'layer by layer' idea reappears in which other problem of the section?

Summary

Spiral = four bounds (top/bottom/left/right) that shrink after each edge.
Always the same sequence of 4 moves; extra checks cover non-square matrices.
O(m·n) time, O(1) extra space.
"Layer by layer" reappears in rotating the image and generating a spiral.

Next lesson: transforming the matrix in place — rotating and zeroing without a copy.

All lessons in this section