Find the station where you can drive the whole loop. If the total gas covers the total cost, an answer exists; whenever the tank goes negative, start again from the next station.
▼The problem
LeetCode 134 (Medium). n stations sit on a circular route; station i gives gas[i] fuel and driving from it to the next costs cost[i]. Starting with an empty tank, return the index of the station where you can start and drive the loop once, or -1 (the answer is unique if it exists).
Example: gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2] → 3 (from station 3 the tank reads 3, 6, 4, 2, 0).
The solution
def can_complete_circuit(gas, cost):
if sum(gas) < sum(cost):
return -1
start, tank = 0, 0
for i in range(len(gas)):
tank += gas[i] - cost[i]
if tank < 0: # ran dry
start, tank = i + 1, 0
return startTranscript
Gas Station. On a circular road, each station gives you some gas, and driving to the next one costs some. Starting empty, find the station where you can drive the whole loop, or return minus one.
Take gas one, two, three, four, five, and costs three, four, five, one, two. Start at station three: gain three, three more, then lose two, two and two. You arrive home empty, so the answer is three.
The simple way tries every start and drives until the tank runs dry: n starts, up to n stations each, n squared time.
Two ideas make it one pass. First, if the total gas is less than the total cost, no start works. Gas two, three, four and costs three, four, three: nine for ten, so minus one. Second, if you start somewhere and run dry, you reached every station on the way with gas to spare. Starting there empty can only be worse, so skip them all.
In code, check the totals first. Then keep a start and a tank. At each station, add gas minus cost. If the tank drops below zero, start at the next station with an empty tank.
Back to the example. Station zero: minus two, dry, start at one. Minus two, start at two. Minus two, start at three. Then plus three, plus three: six in the tank. The answer is three, and that six pays for the stations it skipped.
One pass, so the time is O of n. Just a start and a tank: O of one space.
Check the total, reset when you run dry, never look back. That's Gas Station.