Gas Station
Find a starting station that permits one complete clockwise circuit, or return -1.
Open on LeetCode ↗Intuition
Simulating a full trip from every station is quadratic. A circuit is possible only when total gas covers total cost. During one scan, if the running tank becomes negative at station i, no station between the current candidate and i can succeed because each would begin with an even smaller accumulated prefix. Therefore the next station is the only remaining candidate after that failure.
A circular route with gains and costs often reduces to global feasibility plus a greedy reset. When a negative prefix proves every start within that prefix fails, one linear scan is sufficient.
Approach
Track global fuel feasibility
Add every gas[i] - cost[i] to total. If the final total is negative, the route consumes more fuel than exists and no starting point can work.
Test one candidate with a running tank
Accumulate the same net gain in tank from the current candidate. As long as it stays nonnegative, that candidate can reach the next station.
Discard an entire failed prefix
When tank drops below zero at i, set the candidate to i + 1 and reset the tank. The failed accumulated segment cannot contain a valid start, so no candidate inside it needs separate simulation.
Solution
Common pitfalls
Returning a candidate without checking total fuel
return start
return start if total >= 0 else -1
A locally viable suffix cannot compensate when the complete circuit has a net deficit.
Restarting at the failing station
start = i
start = i + 1
The tank is already negative after processing station i, so i cannot be the new start for the next edge.
Resetting only on zero
if tank == 0:
if tank < 0:
A zero tank is valid when arriving exactly empty; only a negative balance proves failure.
Edge cases
Return -1 regardless of local surpluses.
The running tank remains nonnegative and index zero is returned.
Each negative running balance advances the candidate beyond the entire failed segment.