Gas Station
Along a circular route there are n stations; station i provides gas[i] fuel and it costs cost[i] fuel to drive to the next station. Starting with an empty tank, return the index of the station from which you can complete a full loop, or -1 if impossible. The answer is unique when it exists.
- 1 ≤ n ≤ 10^5
- 0 ≤ gas[i], cost[i] ≤ 10^4
- Feasible iff total gas ≥ total cost
- If the tank goes negative at station j, no start between the current start and j works
- Restart the candidate at j+1 — one pass
When a locally best choice (earliest finish time, largest ratio, farthest reach) can be proved never to hurt the global optimum, you can commit to it without exploring alternatives and get O(n log n) from sorting. The proof usually comes via an exchange argument; if you cannot sketch one, suspect DP instead.
Track the total surplus over all stations and a running tank from the current candidate start. Whenever the tank drops below zero at station j, every start from the candidate through j would also fail there, so set the candidate to j + 1 and reset the tank. After one pass, if the total surplus is non-negative the candidate is the answer, otherwise return -1.
- Prefix sums of
gas − cost: start just after the position of the minimum prefix. Simulating from every start is O(n^2).