Why does one furthest-reach counter decide whether you can cross a river of stones, each stone i allowing a leap of at most a[i] forward?
answer
- what does landing on a stone unlock?
- the reachable set is never scattered
- one number can describe a prefix
- compare index against furthest reach first
- stop when the index outruns the reach
basics
~20 sReachability is monotone: standing on stone i makes every stone up to i + a[i] reachable too. So one pass keeping the maximum of i + a[i], abandoning the crossing as soon as the index passes that maximum, settles it in O(n).
solid answer
~40 sThe leap value is an *at most*, so the set of stones you can stand on is always a contiguous prefix — if index `j` is reachable and `j <= i + a[i]` for some reachable `i`, then `j` is reachable directly. That means the entire reachable set is summarised by a single number: `maxReach`, the largest `i + a[i]` over stones already proven reachable. Sweep left to right; at each index first check `i <= maxReach` (otherwise there is a gap you can never cross, so stop and answer no), then update `maxReach = max(maxReach, i + a[i])`. You answer yes the moment `maxReach >= n - 1`. One pass, O(n) time, O(1) extra space — no table, no search, because monotonicity makes the frontier a single scalar.
go deeper
Be ready to state the rule out loud: standing on a stone makes every stone up to its index plus its range reachable, so one running maximum suffices. Name the costs — linear time, constant extra space.
Explain why the reachable set is always a contiguous prefix, and why the scan must abandon the crossing the moment the index passes the recorded reach instead of finishing the loop and testing at the end.
Defend the linear pass against an interviewer pushing a table-based solution: name the monotonicity that makes one scalar sufficient, and give the variant (exact leaps instead of at-most) under which it collapses.
Own the framing call: when someone proposes heavier machinery for a reachability check, judge whether the monotonicity that licenses the scalar summary actually holds, and weigh the extra code's maintenance cost against zero measured benefit.
## The setting Stones are laid out in a line across a river, indexed `0` to `n - 1`. Standing on stone `i`, you may leap forward by any whole number of stones from `1` up to `a[i]` — the value is a **maximum**, not an exact distance. You start on stone `0`. Question: can you get to stone `n - 1`? The instinct of most candidates is to enumerate: from each stone try every leap length, recurse, memoise. That is a correct but heavy answer — the memoised version is O(n^2) in the worst case (each of `n` stones can branch to up to `n` successors), and the un-memoised version is exponential. The interviewer is looking for the observation that collapses all of it to one scalar. ## The observation: reachability is a prefix Because the leap is *at most* `a[i]`, reaching stone `i` gives you every stone in `[i + 1, i + a[i]]` in one hop — not just the far end of that span. Consequently: > If stone `j` is reachable, then so is every stone `k` with `0 <= k <= j`. Proof sketch: take the hop that lands on `j`, say from `i` with `j <= i + a[i]`. Any `k` with `i < k <= j` also satisfies `k <= i + a[i]`, so it is directly reachable from `i`; induct backwards for `k <= i`. So the reachable set is never scattered — it is always a **contiguous prefix** `[0, R]`. A set that is always a prefix needs exactly one number to describe it: its right endpoint. ## The invariant Sweep `i` from `0` upward and maintain `maxReach = max over all proven-reachable stones j <= i of (j + a[j])` The loop body has two halves and their order matters: 1. **Guard.** If `i > maxReach`, stone `i` is beyond the prefix — no earlier stone's leap covers it, and nothing to the right can help you go backwards. The crossing is impossible; return no. 2. **Extend.** Otherwise stone `i` is genuinely reachable, so fold it in: `maxReach = max(maxReach, i + a[i])`. Answer yes as soon as `maxReach >= n - 1`. The invariant that makes this airtight is: *after processing index `i`, `maxReach` is exactly the furthest index reachable using only stones `0..i`.* Skipping the guard breaks the invariant, because the maximum would then include stones you can never stand on. ## Why the greedy is safe Greedy arguments in this family usually need an exchange argument; here the argument is even simpler — there is no *choice* being made. The algorithm does not pick a hop at all. It computes a set (as a prefix bound) and asks whether the target is in it. Each stone contributes its full potential exactly once, and monotonicity guarantees that contribution is never conditional on which hops you actually took to arrive. Nothing is discarded that could be needed later, which is precisely what a greedy proof has to establish. ## Costs | Approach | Time | Extra space | |---|---|---| | Try every hop from every stone, memoised | O(n^2) | O(n) | | Backwards scan for the last known-good index | O(n) | O(1) | | Furthest-reach forward pass | O(n) | O(1) | ## Edge cases worth naming out loud - **A single stone.** You are already on the far bank; the answer is yes before any leap. The `maxReach >= n - 1` test with `n = 1` handles it because `maxReach` starts at `0`. - **A zero-range stone.** A stone with `a[i] = 0` is a dead stone only if it is the frontier — if some earlier stone's reach already extends past it, it costs nothing. Candidates who say "any zero means failure" are wrong. - **Trailing values do not matter.** The last stone's leap value is irrelevant; you only need to arrive. - **Wide ranges.** If leap values can approach the top of a fixed-width signed accumulator, `i + a[i]` can wrap negative; compare `a[i] >= n - 1 - i` or accumulate in a wider type. ## Where the property fails Change the rule so the leap is **exactly** `a[i]` and the prefix property dies instantly — from stone `0` with `a[0] = 3` you can no longer touch stones `1` and `2`, so the reachable set is scattered and one scalar cannot describe it. That contrast is the cleanest way to show an interviewer you know *why* the linear pass works rather than having memorised it.
- What tells you mid-scan that the crossing is impossible, rather than finding out at the end?The scan index passing the recorded furthest reach. At that point there is a gap: no stone among those proven reachable covers the current index, and stones further right cannot help because leaps only go forward. You can return no immediately instead of finishing the sweep.
- Does the linear pass still work if each stone's value is an exact leap distance rather than a maximum?No. Exact leaps destroy the prefix property — from a stone with value 3 you skip the next two entirely, so the reachable set becomes scattered and a single furthest-reach number no longer describes it. You would have to track the reachable positions themselves, which is a different and heavier computation.
- How would you also report the fewest leaps needed, not just whether crossing is possible?Feasibility and hop count are different questions: the furthest-reach scalar answers only the first. Counting minimum hops needs a second piece of state — the end of the span covered by the hops committed so far — and a counter that ticks when the sweep exhausts that span.
The reach is like a flashlight beam sweeping ahead of you: every step forward may lengthen it, and you are stuck the moment you step past where the beam ends.
saying these in an interview costs you the question
- Claims reachability needs a table or a search, never a linear pass
- Says every possible leap length from each stone must be simulated
- Thinks any stone with range zero makes the crossing impossible
- Folds in i + a[i] without first checking the index is reachable
- Believes the last stone's leap value affects the answer