There are n gas stations on a circular road. Station i gives gas[i] units of fuel, and driving from station i to station i + 1 uses cost[i] units. You start with an empty tank at some station. Return the index of the station from which you can drive around the whole circle once, or -1 if no such station exists. If an answer exists, it is unique.
- 1 <= n <= 10^5
- 0 <= gas[i], cost[i] <= 10^4
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force tries every start and simulates the full loop: O(n^2). Two facts make it O(n). First, if sum(gas) >= sum(cost) an answer exists. Second, suppose we start at s and the tank first goes negative after station i. Every station k between s and i arrived with a tank of at least 0 when we passed it, so starting at k with an empty tank is no better and would also fail by i. So we can skip all of them and try i + 1 as the next start. The greedy is safe because it only discards starts that are proven to fail.
Algorithm
- Track
total(sum ofgas[i] - cost[i]over all stations),tankandstart = 0. - For each
i, addgas[i] - cost[i]to bothtotalandtank. - If
tank < 0, setstart = i + 1andtank = 0. - At the end, return
startiftotal >= 0, else-1.
O(n)Space: O(1)start and i is safe. Interviewers ask for that proof more than for the code itself.class Solution: def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int: total = tank = start = 0 for i in range(len(gas)): d = gas[i] - cost[i] total += d tank += d if tank < 0: # no start in [start, i] works start = i + 1 tank = 0 return start if total >= 0 else -1