Stations are arranged in a circle. At station i you gain gas[i] fuel, and driving to station i+1 costs cost[i]. Starting with an empty tank, return the index you must start from to complete the loop, or -1 if it is impossible. The answer is guaranteed unique if it exists.
Restating the Problem: You have a car that starts with zero fuel. You must pick a starting station on a circular route. At each station, you pump gas[i] into your tank, and driving to the next station consumes cost[i]. You must complete the circle without your fuel ever dropping below 0.
Constraints to note: The arrays gas and cost have the same length N, which can be up to 10^5. This implies we need an O(N) algorithm.
Edge cases: The net gas might be exactly zero at the end; this is a valid trip, provided you don't drop below zero midway.
Work with the net gain at each station, gas[i] - cost[i]. Now the question is: from which starting point can you go all the way round without the running total ever dropping below zero?
Two facts do all the work, and both need proving.
Fact 1 — a solution exists exactly when the total net gain is non-negative.
If the total is negative, you burn more fuel than you collect over a full loop, so no start can work. If it is non-negative, a valid start is guaranteed to exist. The first direction is obvious; the second falls out of Fact 2.
Fact 2 — if you run out of fuel travelling from start to i, then no station between them works either.
This fact is what makes the algorithm one pass, so here is the proof. Suppose you start at start and fail on the way to station i. Take any station j strictly between them. You arrived at j with a non-negative tank, otherwise you would have failed earlier than i. Starting at j instead means arriving at each later station with less fuel than before. So you fail at i too, or sooner.
So the whole stretch from start to i can be skipped in one step. Every index is tested at most once, and the scan is linear.
class Solution: def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int: if sum(gas) < sum(cost): # (1) return -1 # not enough fuel in total start = 0 # (2) tank = 0 # (3) for i in range(len(gas)): # (4) tank += gas[i] - cost[i] # (5) if tank < 0: # (6) cannot reach station i+1 start = i + 1 # (7) skip the whole stretch tank = 0 # (8) start fresh from there return start # (9)
ts
function canCompleteCircuit(gas: number[], cost: number[]): number { const total = gas.reduce((a, b) => a + b, 0) - cost.reduce((a, b) => a + b, 0); // (1) if (total < 0) return -1; let start = 0, tank = 0; // (2) for (let i = 0; i < gas.length; i++) { // (4) tank += gas[i] - cost[i]; // (5) if (tank < 0) { // (6) start = i + 1; // (7) tank = 0; // (8) } } return start; // (9)}
(1) If there is less fuel in total than the trip needs, no start can work. Return −1. If there is enough in total, the problem promises exactly one start works, and the rest of the code finds it.
(2) The candidate starting station.
(3) Fuel in the tank since that start.
(4) Drive through every station once.
(5) Fill up at station i, then pay the fuel to reach station i + 1.
(6) The tank went negative, so we cannot reach station i + 1 from start.
(7) Then no station from start to i can be the answer either, so the next candidate is i + 1. Here is why. Every station between start and i was reached with a tank of zero or more. Starting at one of them means arriving there with an empty tank instead, which is no better. So starting there would also run dry before i + 1.
(8) The new candidate starts with an empty tank.
(9) The last candidate standing is the answer. Line (1) already confirmed there is enough fuel overall, so the trip from this start never runs dry.
No wraparound is needed anywhere. That looks wrong for a circular problem, and it is not.
Once the total check has passed, a valid start exists. The scan finds the last position from which the tank never goes negative through to the end of the array. Because the overall total is non-negative, the fuel accumulated across the skipped prefix is enough to cover the wrap. So the remaining stretch plus the wrap succeeds, and there is nothing to simulate.
Code Walkthrough:
Initial Viability Check (sum(gas) < sum(cost)): We immediately rule out impossible cases. If the total gas available across all stations is less than the total cost to travel, no starting point can possibly work.
Iteration: We loop through each station i. We track our current tank level and our proposed start index.
Accumulate Fuel: At each step, we add the net gain (gas[i] - cost[i]) to our tank.
Handling Failure (tank < 0): If the tank drops below zero, it means we cannot reach station i+1 from our current start. Due to Fact 2, we know no station between start and i could have worked either. So, we make i+1 our new proposed start and reset tank to 0.
Return: If we finish the loop, start holds the correct answer (guaranteed by the initial sum check).
tank resets to 0 on failure, because you are now considering a fresh journey beginning at i + 1.
The uniqueness guarantee is what lets the code return the first candidate it finds without checking whether an earlier one also works.
Maximum Subarray — the same "reset when the running total goes negative" rule, and the same exchange argument behind it. 4.26.1.
Maximum Sum Circular Subarray — circular again, handled by splitting into wrapping and non-wrapping cases.
Candy — another greedy that needs two passes and a proof.
The transferable idea: when a failed attempt rules out a whole range of alternatives, the outer loop disappears. That is the same reasoning as the run-start guard in 4.4.9 and the discard proofs in 4.5.
"Why does a non-negative total guarantee a solution?" Because of Fact 2 — the scan always terminates at a start whose remaining stretch works, and the total guarantees the wrap is covered.
"Why can you skip the whole stretch after a failure?" The proof above: any intermediate station is reached with a non-negative tank, so starting there gives you no more fuel at any later point.
"Why is there no wraparound in the code?" The total check has already accounted for it.
"What if the answer were not unique?" The code returns the first valid start it finds, which is still a correct answer. If you needed all of them, you would collect every candidate and verify each — O(n^2) worst case.
"What is the brute force?"O(n^2), and Fact 2 is what kills the outer loop.
One thing to volunteer: give Fact 2 with its proof before writing the code. This problem is short but almost impossible to justify without it, and an unjustified greedy is a guess.