Spiral Matrix
WHAT IT SAYS
Print every element of an m x n matrix in spiral order: left to right along the top, down the right side, right to left along the bottom, up the left side, and inwards.
WHAT IT'S REALLY ASKING
"Walking a spiral by feel means remembering every cell you have stepped on. But look at what is left after you strip the top row off: another rectangle. Strip its right column: still a rectangle. If the unvisited region is always a rectangle, what is the smallest thing you could possibly need to remember?"
Walk and turn when blocked
O(m*n) time, O(m*n) extra spaceKeep a direction and a visited matrix. Step forward; if the next cell is off the edge or already visited, turn right. Stop after m*n cells. It is a faithful simulation of what your finger does.
WHERE THE WORK IS WASTED — You are storing m*n booleans to answer a question the shape of the problem already answers. Print the visited grid at any moment and you will never see a ragged, arbitrary set of marks — it is always exactly a frame around an untouched rectangle. You are spending an entire matrix to encode four integers, and the turn test re-derives 'am I at the boundary?' from raw data on every single step instead of just knowing where the boundary is.
What is left after every pass is always a rectangle.
Prove it by induction on the passes. Start: the unvisited region is the whole matrix, rows top..bottom and columns left..right — a rectangle. Now traverse the top row completely. What remains unvisited is rows top+1..bottom, columns left..right. Still a rectangle. Traverse the right column completely: rows top+1..bottom, columns left..right-1. Still a rectangle. The bottom row, then the left column, do the same. The invariant never breaks — and it never breaks precisely because each leg of the spiral consumes an entire edge of the current rectangle, not a partial one. So 'visited' is never an arbitrary set. It is the complement of a rectangle, and a rectangle is four integers. The visited matrix was storing a fact that four counters store exactly. One consequence is subtle and it is where nearly everyone's code breaks. After the top row and the right column have been eaten, the surviving rectangle may have collapsed — it can be a single row, or a single column, or nothing at all. In that degenerate case the 'bottom row' you are about to walk right-to-left IS the top row you already walked left-to-right, and you will print it twice, backwards. That is why the bottom and left legs must be guarded with 'only if top is still <= bottom' and 'only if left is still <= right'. Those guards are not defensive noise; they are the invariant defending itself.
Four walls, closing in
O(m*n) time, O(1) extra space beyond the outputHold top, bottom, left, right. Walk left-to-right along top, then top++. Walk top-to-bottom along right, then right--. If top is still <= bottom, walk right-to-left along bottom, then bottom--. If left is still <= right, walk bottom-to-top along left, then left++. Repeat while top <= bottom and left <= right — every element is emitted exactly once because every leg consumes a full edge of a rectangle that is strictly shrinking.
Peel the Rectangle
YOU'LL SEE IT AGAIN WHEN
- A traversal where the already-done region always has a describable shape — a frame, a prefix, a border — rather than an arbitrary scatter of cells.
- After one pass, the leftover problem is a smaller instance of the same problem, so the state is 'which sub-region am I on', not 'where have I been'.
- Movement is fully deterministic and never depends on the values in the cells, so any bookkeeping about the path is redundant with the geometry.