In a spiral-order walk with top, bottom, left and right bounds, why recheck the bounds mid-lap?
answer
- Which bounds change inside one lap?
- The loop condition is stale by pass three
- Try a chart that is one row tall
- Count emitted cells against rows times columns
- The last lap of every walk hits this
basics
~20 sA lap can exhaust the region halfway through. Once the top row and right column are consumed, what remains may be a single row or column, and without rechecking the bounds the return passes walk it twice.
solid answer
~50 sThe four bounds shrink *inside* one lap, not just between laps, so the loop condition checked at the top of the lap can be stale by the time you reach the third and fourth passes. Concretely: after visiting the top row you raise `top`, and after the right column you lower `right`. If the region was one row tall, `top` is now past `bottom`, and the bottom-row pass would re-walk that same row right-to-left; if it was one column wide, the left-column pass would re-walk the column upward. Guarding the third pass with `top <= bottom` and the fourth with `left <= right` is what makes a walk of an `m x n` region emit exactly `m * n` cells. The cases to test are the empty region, a single row, a single column, and an odd square whose innermost remainder is one cell.
code
pseudocode · 12 linestop = 0; bottom = rows-1; left = 0; right = cols-1
while top <= bottom and left <= right
for j in left..right: visit(m[top][j])
top = top + 1
for i in top..bottom: visit(m[i][right])
right = right - 1
if top <= bottom
for j in right downto left: visit(m[bottom][j])
bottom = bottom - 1
if left <= right
for i in bottom downto top: visit(m[i][left])
left = left + 1go deeper
Know the lap structure — top row, right column, bottom row, left column — and that each pass moves its bound inward. Practise on a one-row and a one-column chart, since those are where a first attempt breaks.
Explain that top and right change mid-lap, so the loop condition is already stale at the third pass, and say exactly which duplicate each missing guard produces. Give the time and extra-space costs.
Show how you would prove it rather than patch it: state the shrinking-rectangle invariant, list the four boundary shapes you test, and assert the emitted count so a duplicate fails loudly instead of hiding in a long sequence.
Argue for the formulation the team can verify. Direction-vector walks with a turn rule and bound-shrinking walks solve the same problem; pick one, state its invariant in the code, and cover the whole family with a property test against a reference.
## The shape of the walk A boundary walk in spiral order keeps four indices describing the un-visited rectangle — `top`, `bottom`, `left`, `right` — and repeats a four-pass lap: the top row left-to-right, the right column downward, the bottom row right-to-left, the left column upward. After each pass the corresponding bound moves inward by one. ``` top = 0; bottom = rows-1; left = 0; right = cols-1 while top <= bottom and left <= right for j in left..right: visit(m[top][j]) top = top + 1 for i in top..bottom: visit(m[i][right]) right = right - 1 if top <= bottom for j in right downto left: visit(m[bottom][j]) bottom = bottom - 1 if left <= right for i in bottom downto top: visit(m[i][left]) left = left + 1 ``` ## Why the two guards exist The loop condition is evaluated once, at the top of the lap. Both `top` and `right` then change **during** the lap. So by the time control reaches the third pass, the rectangle may already be empty, and the condition that authorised the lap no longer holds. Walk a seating chart that is one row tall — three seats in a single row. The lap visits all three seats left-to-right and raises `top` to 1, which is now greater than `bottom = 0`. The right-column pass is naturally empty. Without the `top <= bottom` guard, the bottom-row pass would walk row 0 again, right-to-left, and every seat would be reported twice. A chart one column wide is the mirror image: the top-row pass takes one seat, the right-column pass takes the rest going down, `right` drops below `left`, and without the `left <= right` guard the left-column pass walks the same column back upward. The same collision happens on the **last lap of any region**, not only on degenerate inputs. An odd square finishes with a one-by-one remainder; a five-by-three finishes with a one-row remainder in the middle. That is the important point to make in an interview: the guards are not special-casing weird inputs, they are handling the ordinary end of every walk. ## Why `for` bounds alone are not enough A common half-fix is to rely on empty ranges: `for i in top..bottom` is naturally empty when `top > bottom`. That saves the **column** passes, whose ranges do invert, but not the **row** passes, whose ranges do not. In the single-row case the bottom-row pass runs `for j in right downto left` with `right = 1` and `left = 0` — a perfectly non-empty range over a row that has already been visited. The range is valid; the *row index* is stale. Empty-range reasoning cannot rescue you, which is exactly why the explicit bound check goes on the third and fourth passes. ## The cost, and the invariant to state Every cell is visited exactly once, so the walk is `Theta(m * n)` time. Extra space is `O(1)` beyond whatever holds the output: four indices, no per-cell bookkeeping and no marker structure. If someone reaches for a same-sized grid of flags to avoid double-visits, they have replaced an invariant with an allocation — the bounds already encode which cells remain. The invariant worth saying out loud: *at the top of each lap, the un-visited cells are exactly the rectangle `[top..bottom] x [left..right]`, and every pass both visits a full edge of that rectangle and shrinks it by one.* Every off-by-one in this family of walks is a violation of that sentence — a pass that visits an edge without shrinking, or shrinks without visiting, or visits an edge of a rectangle that is already empty. ## The test list Four cases catch essentially every implementation bug here: an empty region (the walk must emit nothing rather than dereference `m[0][0]`), a single row, a single column, and a square with an odd side. Add one rectangle taller than it is wide and one wider than it is tall, and assert the *count* of emitted cells as well as their order — a duplicate shows up as a count of `m * n + k` long before you can spot it by reading the sequence.
- Can you rely on the for-ranges being empty instead of writing the guards?Only for the column passes. When `top > bottom`, `for i in top..bottom` is empty and the column pass costs nothing. But the row passes iterate over columns, and `left` and `right` can still form a valid range while the row index itself is stale — so the bottom-row pass happily re-walks an already-visited row. The row index, not the range, is what has gone out of bounds.
- State the loop invariant that makes this walk obviously correct.At the top of every lap, the not-yet-visited cells are exactly the rectangle rows `top..bottom` by columns `left..right`. Each pass visits one complete edge of that rectangle and then retracts the matching bound by one, so the rectangle strictly shrinks and the visited set never overlaps it. The walk ends when the rectangle is empty, having emitted every cell once.
- How would you emit the same chart in diagonal order instead?Group cells by the constant `d = i + j`: every cell on one anti-diagonal shares that sum. An `m x n` grid has `m + n - 1` diagonals, `d` running from `0` to `m + n - 2`. For a given `d`, the row index runs from `max(0, d - (n - 1))` to `min(d, m - 1)` with `j = d - i` — those two clamps are the whole difficulty, and deriving them beats memorising them.
- What does the walk cost in time and extra space?`Theta(m * n)` time, since each cell is visited exactly once, and `O(1)` extra space beyond the output — just the four bound indices. No per-cell marking is needed: the bounds already describe precisely which cells remain, so a same-sized grid of flags would be an allocation standing in for an invariant.
saying these in an interview costs you the question
- Thinks the loop condition is enough on its own
- Handles single-row and single-column as special cases only
- Allocates a same-sized marker grid to avoid duplicates
- Believes empty for-ranges protect the row passes
- Never checks the emitted count against rows times columns