Given circular gas stations, each with a gas supply and a travel cost to the next station, the machine must find the starting station that allows a full lap, or return -1. The tank starts empty and the route must complete without the fuel ever dropping below zero.
The key insight is a global invariant: a complete lap is possible if and only if the total gas is at least the total cost. And when it is possible, the answer is unique, so the machine can find it in a single sweep instead of trying every start.
The approach runs in three steps. First, accumulate the net surplus across all stations and track the running surplus in a second variable. Second, whenever the running surplus drops below zero, the route fails at the current prefix, so discard every station before the next one and restart the surplus there — the candidate start becomes the next station. Third, return the candidate if the total surplus is nonnegative, otherwise -1. Time is O(n) and space is O(1).
The trickiest edge case is the route that barely succeeds: surplus can hit exactly zero mid-lap, which is fine because zero fuel still reaches the next station. The machine must only reset the start on strictly negative surplus, and the total-net check is what separates "one exact fit" from "impossible".
def canCompleteCircuit(gas, cost):
total, surplus, start = 0, 0, 0
for i in range(len(gas)):
diff = gas[i] - cost[i]
total += diff
surplus += diff
if surplus < 0:
start = i + 1
surplus = 0
return start if total >= 0 else -1