On a circular route with gain[i] at each stop and cost[i] to the next, why is the single-pass restart greedy correct?
answer
- add up the whole loop first
- work in surplus per leg, not gain alone
- where is the running balance at its lowest?
- one failure condemns every stop in the span
- restart after the stop you ran flat on
basics
~20 sTwo facts carry it. A feasible start exists exactly when total gain over the loop is at least total cost. And if a run starting at s dies before reaching stop j, every stop between them dies no later, so the scan can skip them all and restart after j — one lap, O(n) time, O(1) space.
solid answer
~50 sWork with per-leg surplus `s[i] = gain[i] - cost[i]`. **Existence:** if the surplus over the whole loop is negative, no start survives a full lap, since a lap from any start sums the same terms; if it is non-negative, a start exists — begin immediately after the position where the running surplus is at its minimum, and every subsequent prefix is non-negative by construction. **The restart:** suppose a drone leaving stop `s` runs flat somewhere before stop `j`. Then the partial sum from `s` to any stop `k` in `(s, j]` was non-negative up to `k` — otherwise the drone would have died earlier — so a run starting at `k` inherits an even smaller running balance and dies no later than `j` too. Every candidate in `[s, j]` is therefore eliminated by the single failure, and the scan resumes at `j + 1` without re-testing any of them. One lap, constant extra state, no wraparound simulation.
go deeper
Know the aggregate rule: if the loop's total gain is less than its total cost, no starting stop can work at all. Be able to compute per-leg surplus and sum it.
Explain the algorithm's three pieces of state — candidate start, running balance, total surplus — and say exactly when the balance resets to zero and why the candidate moves to the stop after the failure.
Prove both halves out loud: why a non-negative total guarantees some start exists, and why one failed run eliminates every candidate inside the span it covered. Name the reset-the-balance bug and the zero-total boundary.
Own the generalisation and its limits: the pattern pairs an aggregate feasibility check with a local elimination rule, and it depends on the route closing into a circle. Judge whether a proposed variant still satisfies that precondition before reusing the argument.
## The setting A delivery drone flies a circular route of `n` stops with battery-swap stations. At stop `i` it takes on `gain[i]` units of charge; flying from stop `i` to stop `i + 1` (wrapping after the last) costs `cost[i]`. The drone starts empty and must never go flat mid-leg. Which stop can it start from and complete a full loop? Report one, or report that none exists. Define the **per-leg surplus** `s[i] = gain[i] - cost[i]`. The whole problem is now about running sums of `s` around a circle. ## Claim 1 — a feasible start exists if and only if the total surplus is non-negative *Necessity.* A complete lap from any start visits every stop exactly once, so its total is `sum(s)` regardless of where it began. If that total is negative, the balance is negative at the end of the lap, and a balance that is negative at the end went negative somewhere. No start works. *Sufficiency.* Suppose `sum(s) >= 0`. Lay the loop out linearly and let `P[k] = s[0] + ... + s[k]` be the running prefix sums. Let `m` be an index where `P` attains its minimum, and consider starting at `m + 1`. For a stop `k` after `m`, the balance on arrival is `P[k] - P[m] >= 0` because `P[m]` is the minimum. For a stop `k` that wraps around past the end, the balance is `sum(s) - P[m] + P[k] >= P[k] - P[m] >= 0`, using `sum(s) >= 0`. So no prefix of the journey from `m + 1` is ever negative: the start is feasible. That proof is worth being able to sketch out loud, because it explains *why* an aggregate check answers a question about a worst moment. ## Claim 2 — one failure eliminates a whole span The single-pass algorithm carries a candidate start `start`, a running balance `tank` since that start, and the total surplus `total`. Walk `i` around once, adding `s[i]` to both. Whenever `tank` goes negative, set `start = i + 1` and `tank = 0`. At the end, answer `start` if `total >= 0`, otherwise report none. Why is skipping safe? Say the run from `start` first goes negative at leg `j`. For any candidate `k` strictly between `start` and `j`, the partial sum from `start` up to just before `k` was non-negative — the drone got there alive. A run that begins at `k` therefore starts with balance `0` instead of that non-negative amount, so at every later stop up to `j` its balance is **less than or equal to** the original run's. Since the original went negative at `j`, so does the run from `k`, no later. Every candidate in the span is condemned by that one failure, and the scan can jump past all of them. That is the exchange-style argument that turns an O(n^2) "try every start" into O(n). ## Why one lap, and only one A naive reading suggests you might need to simulate the wraparound to confirm the surviving candidate. You do not: Claim 1 already guarantees that *some* start works when `total >= 0`, and Claim 2 guarantees the scan never discarded a working one. So the final `start` must be feasible — no second lap, no doubled array, no simulation past the end. This combination of an aggregate feasibility check with a local elimination rule is the memorable part of the pattern. ## Costs and edge cases - **O(n) time, O(1) extra space.** Two accumulators and an index. - **Multiple feasible starts** are possible; the algorithm returns one, and the question rarely asks for all of them. Do not claim uniqueness — it does not hold in general. - **Exactly zero total surplus** is feasible: the drone arrives home empty, which is allowed. Off-by-one thinking that requires a strict surplus wrongly reports failure. - **Individual legs may have negative surplus** and that is normal; only the running balance and the total matter. - **A single stop** is feasible when its own surplus is non-negative, which the same rule already covers. - **Failing to reset the balance to zero on restart** is the common implementation bug: carrying a negative balance forward corrupts every later candidate. ## A boundary worth naming The argument leans on the route being a **circle**. On an open line — start anywhere, finish at the far end, no wraparound — the total-surplus equivalence is false: a line can have a positive total and still have no viable start, because the deficit may sit at the very front where no later gain can prepay it. Recognising that the wraparound is load-bearing, rather than incidental scenery, is what separates a candidate who reproduces the algorithm from one who understands it.
- Without the restart trick, how would you locate the start directly from the running surpluses?Take prefix sums of the per-leg surpluses around the loop and find the index where that running total is at its minimum; start at the stop immediately after it. Every later balance is measured against the lowest point, so no prefix of the journey can be negative once the total surplus is non-negative.
- Does the argument survive if some legs have negative cost — a downhill leg that recharges the drone?Yes. Nothing in either claim assumes the individual gains or costs are non-negative; both work purely with the per-leg surplus and its running sums. A recharging leg is just a leg with a larger surplus, and the total-versus-minimum-prefix reasoning is unchanged.
- What changes if the route is an open line rather than a closed loop?The equivalence collapses. On a line there is no wraparound, so a positive total no longer guarantees a viable start — a large deficit at the front can never be prepaid by gains behind it. Feasibility from a given start becomes a prefix condition on that start alone, and the aggregate check stops being sufficient.
- Is the feasible start unique when one exists?No. A loop with slack can admit many valid starts — in the extreme, if every leg has non-negative surplus, every stop works. The algorithm returns one witness, and claiming uniqueness is a common overreach that an interviewer will probe with exactly that all-non-negative example.
It is like walking a circular hiking trail with water caches: whether the trail is walkable at all depends only on total water versus total thirst, while where to start depends only on the driest point.
saying these in an interview costs you the question
- Says every possible start must be simulated, accepting quadratic cost
- Thinks a start works if its own gain exceeds its own leg cost
- Claims a non-negative total surplus does not guarantee any start
- Restarts at the failing stop instead of the one after it
- Forgets to reset the running balance to zero on restart
- Asserts the feasible start is unique when one exists