The problem
Gas stations stand in a circle. Station i gives gas[i] units, and driving from station i to the next costs cost[i]. You start with an empty tank at a station of your choice.
Return the station from which you can drive all the way round once, or −1 if none. If a start exists, it is unique.
Examples
- Input
gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]
- Output
3
- Input
gas = [2, 3, 4], cost = [3, 4, 3]
- Output
-1
Constraints
- 1 ≤ n ≤ 10⁵
- 0 ≤ gas[i], cost[i] ≤ 10⁴
The idea
If the total gas is less than the total cost, no start works. Otherwise one does — and it can be found in one pass.
Drive from station 0, keeping a running tank. If it goes negative after station i, then no station from the current start up to i can be the answer: each of them would arrive at i + 1 with no more gas than this attempt had (it would have skipped the stations before it, which added a non-negative amount). So restart at i + 1 with an empty tank. The last restart is the answer.
- Time
- O(n)
- Space
- O(1)
Solution · every language run against every case
class Solution: def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int: # If there is less gas than cost in total, no start works. Otherwise the answer is the # station after the last point where the running tank went negative: no start at or # before that point can get past it. if sum(gas) < sum(cost): return -1 start = tank = 0 for i in range(len(gas)): tank += gas[i] - cost[i] if tank < 0: start, tank = i + 1, 0 return start