A reachability scan takes the maximum of i + a[i] over every stone but never compares i to that maximum — what breaks?

## What the loop is supposed to maintain A furthest-reach reachability scan over stones — stone `i` permits a leap of at most `a[i]` forward — rests on one invariant: > After processing index `i`, `maxReach` equals the furthest index reachable from stone `0` using only stones `0..i`. The word doing all the work is *reachable*. A stone contributes its range to the frontier only if you can actually stand on it. Drop the guard and the loop computes something else entirely: the maximum of `i + a[i]` over all indices, reachable or not. That quantity is an over-estimate, and over-estimating reachability produces **false positives** — the worst kind of bug here, because the algorithm confidently answers yes on inputs that strand you. ## The trace that exposes it Leaps `[1, 0, 0, 5]`, so `n = 4` and the goal is index `3`. | i | a[i] | true reachable? | unguarded maxReach | |---|---|---|---| | 0 | 1 | yes | max(0, 0+1) = 1 | | 1 | 0 | yes | max(1, 1+0) = 1 | | 2 | 0 | **no** | max(1, 2+0) = 2 | | 3 | 5 | **no** | max(2, 3+5) = 8 | Final test `8 >= 3` returns crossable. The truth: from stone `0` you can only leap to stone `1`, whose range is `0`, so you are stuck. Index `2` was never standable, and the moment the loop folded index `2` into the reach it manufactured a foothold that does not exist — after which index `3` looked reachable, and its enormous range finished the job. Note how the failure is engineered: an early dead stone, then a large range parked just past the gap. Random inputs rarely expose it, which is exactly why this bug survives casual testing and shows up in a review. ## The fix Guard first, extend second: 1. If `i > maxReach`, the current index sits past the reachable prefix — return not-crossable. 2. Otherwise `maxReach = max(maxReach, i + a[i])`. Order matters: extending before guarding would let the current stone rescue itself. Some write the equivalent as a loop bound (`while i <= maxReach and i < n`), which is the same idea expressed in the control flow rather than the body. ## The other boundary cases in the same family - **A single stone.** `n = 1` means you are already across, and the answer must be yes before any leap is attempted. A loop that unconditionally requires a positive range on the first stone gets this wrong. - **Trailing zero range.** The last stone's range is irrelevant — you need to arrive, never to leave. Code that special-cases it is confused. - **Fixed-width overflow.** If ranges can approach the maximum of a signed 32-bit accumulator, `i + a[i]` wraps to a negative value and the reach *collapses* rather than growing, turning a crossable input into a reported failure. The safe comparison is `a[i] >= n - 1 - i`, which never adds two large values, or accumulate in a wider type. - **Zero-length input**, if the caller can produce one, needs a defined answer before the loop, not inside it. ## How to talk about it in an interview When asked to test your own code, do not read the loop back line by line. Name the *class* of input each bug needs: one input where a gap precedes a large range (catches the missing guard), one input of length one (catches the initialisation), one input with a zero range that is jumped over rather than landed on (catches over-eager failure), and one input with values near the accumulator's ceiling (catches overflow). Four inputs, each aimed at a specific way the invariant can be violated, is a far stronger answer than a dozen random arrays — and it demonstrates that you know what the invariant *is*, which is the actual thing being assessed.