One pass with a reset

Two separate facts, each cheap: whether an answer exists at all, and where it must be.

Why it works

Where must it be?

Walk once, carrying the running balance. Whenever the balance goes negative, no stop from the current candidate start up to here can work, because starting later within that stretch only removes non-negative prefixes and cannot help.

So discard all of them at once: set the candidate start to the next stop and reset the balance. One pass, and the candidate that survives to the end is the answer.

That is the exchange argument in a different shape. Rather than showing the chosen option is safe, it shows a whole block of options is provably unsafe and can be discarded together.

The running balance is the thing to watch. Below it is printed per stop, along with the moment a whole block of candidates gets thrown away.

1gains = [1, 2, 3, 4, 5]2costs = [3, 4, 5, 1, 2]3 4balance = 05for stop in range(len(gains)):6    balance += gains[stop] - costs[stop]7    if balance < 0:8        print(f"stop {stop}: balance {balance} -> starts 0 through {stop} are all out")9        balance = 010    else:11        print(f"stop {stop}: balance {balance}")

Three separate collapses rule out three starts, and the survivor is stop 3.

Quick check· 5 min

Why can the whole stretch be discarded?

The running balance goes negative at stop k, having started the current attempt at stop s. Why can every stop from s to k be ruled out at once?

Every prefix from s up to before k had a non-negative balance, so starting later within that stretch removes only non-negative amounts and still fails by kBecause the total gain must be less than the total cost for the balance to go negativeBecause stops before k cannot reach k without passing through sThey cannot all be ruled out; each must be simulated separately, which is why the algorithm is quadratic

Problem· 28 min

Gas Station

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1gains = [1, 2, 3, 4, 5]2costs = [3, 4, 5, 1, 2]3 4balance = 05for stop in range(len(gains)):6 balance += gains[stop] - costs[stop]7 if balance < 0:8 print(f"stop {stop}: balance {balance} -> starts 0 through {stop} are all out")9 balance = 010 else:11 print(f"stop {stop}: balance {balance}")