When counting minimum relay hops across towers with forward ranges r[i], what does the correct greedy maximize at each step?

## The setting A line of relay towers, indexed `0` to `n - 1`. Tower `i` can transmit forward to any tower within `r[i]` positions. You start at tower `0` and want the message at tower `n - 1` in as few hops as possible. Assume the last tower is reachable (feasibility is a separate check). ## The tempting wrong answer "Always transmit as far as you can." It sounds like the obvious greedy and it is wrong. Take ranges `[2, 5, 1, 1, 1, 1]`. Full-range hopping goes `0 -> 2`, and tower `2` has range `1`, so `2 -> 3 -> 4 -> 5`: **four hops**. The optimum is `0 -> 1 -> 5`: **two hops**, because tower `1` is nearer but carries a vastly longer range. The lesson generalises: the value of a landing spot is not its distance from you, it is its distance *plus its own range*. A candidate who repairs this to "hop to the reachable tower maximising `i + r[i]`" now has a correct greedy — and the window formulation is exactly that idea written so it needs only one pass. ## Windows, not landings Think in bands. After zero hops you can only be at tower `0`. After one hop you can be at any tower in `[1, 0 + r[0]]`. After two hops you can be at any tower in the span reachable from anywhere in that first band. Each hop count owns a contiguous band, and the bands are nested and monotone — this is the same prefix monotonicity that makes reachability linear, applied one layer at a time. So the algorithm carries two numbers: - `windowEnd` — the furthest tower coverable with the hops counted so far. - `furthest` — the best `i + r[i]` seen while sweeping the current band. Sweep `i` upward. Always fold `i` into `furthest`. When `i == windowEnd`, the current hop budget is exhausted: charge one more hop and set `windowEnd = furthest`. Note that the hop count is incremented when you *leave* a band, so no tower is ever explicitly chosen as the landing spot — the algorithm commits only to the band boundary, and the decision of which tower to land on is deferred until it no longer matters. ## Why the loop stops one short The sweep runs to `n - 2`, not `n - 1`. Touching the last tower would charge a hop for leaving a band you never need to leave — you are already there. This off-by-one is the single most common bug in the pattern; the giveaway symptom is an answer that is exactly one too large on every input. ## Correctness in one line By induction: if `windowEnd` is exactly the furthest tower reachable in `k` hops, then the maximum of `i + r[i]` over all `i <= windowEnd` is exactly the furthest tower reachable in `k + 1` hops, because reaching the message to any tower in that band takes `k` hops and one more hop extends from the best of them. The greedy is safe because it never discards a candidate: every tower in the band contributes its reach before the band boundary is crossed. ## Costs and edge cases - **Time O(n), extra space O(1).** Each tower is visited once and never revisited; the bands partition the line rather than overlapping it. - **Already at the destination** (`n == 1`): zero hops, and the loop body never runs. - **A zero-range tower inside a band** is harmless — the band's reach comes from the best member, not every member. - **Feasibility is a precondition.** If the last tower is not reachable, this loop still returns a number; it does not detect the failure. Either run the reachability check first or add a guard for the case where `furthest` fails to exceed `windowEnd` when the band is exhausted. - **Wide ranges** risk `i + r[i]` overflowing a fixed-width signed accumulator; clamp or widen if ranges can approach the accumulator's maximum. ## What the interviewer is really testing Two things. First, whether you can produce a concrete counterexample to the naive greedy on demand — that is the difference between having reasoned about it and having memorised it. Second, whether you can articulate the layer/band framing, because it is the reusable idea: the same shape reappears whenever the cost is a hop count over a monotone reachable frontier.