Gas Station

Gas Station looks intimidating — a circular road, fuel, costs — but it collapses into a single greedy pass. It teaches a beautiful insight: when a stretch of road is impossible, you can skip all of its starting points at once.

The slow way first

The obvious idea: try every station as a starting point, and for each one simulate the full loop to see if the tank ever drops below zero. That is O(n²) — for each of n starts we may walk up to n stations.

The question to ask: when a start fails, what have I actually learned? It turns out a single failure rules out many starts at once, and that is what makes one pass enough.

The idea: skip whole failed stretches

Two facts do all the work:

1. If total gas ≥ total cost, a valid start exists. Otherwise the answer is -1.
2. If the tank goes negative somewhere between start and i, then no station in that range can be the answer. So the next possible start is i + 1, and we reset the tank to zero.

Walk the array once, adding gas[i] - cost[i] to a running tank. Every time the tank dips below zero, jump start to the next station and zero the tank. Whatever start you are sitting on at the end is the answer.

The key insight: a negative tank invalidates every start in the failed stretch, not just the current one — so we never have to re-examine them.

Walk through it

Step through the animation. The pointer i scans left to right over the gas and cost rows. The tank goes negative at stations 0, 1, and 2, so start keeps jumping forward. At station 3 the tank finally stays positive, and it survives to the end — so start = 3 is the answer.

Pseudocode

if sum(gas) < sum(cost):
    return -1                       # not enough fuel overall
start = 0
tank = 0
for each station i:
    tank = tank + gas[i] - cost[i]
    if tank < 0:                    # this stretch is impossible
        start = i + 1               # next candidate start
        tank = 0                    # reset the tank
return start

The Python solution

def can_complete_circuit(gas, cost):
    if sum(gas) < sum(cost):
        return -1
    start = 0
    tank = 0
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0:
            start = i + 1
            tank = 0
    return start

• The first check (sum(gas) < sum(cost)) handles the impossible case up front and guarantees the rest finds a real answer.
• start is our current best guess for the starting station; tank is the running fuel since that guess.
• tank += gas[i] - cost[i] is the net fuel change for the leg out of station i.
• Lines 8-10 are the heart of it: when the tank goes negative, the whole stretch from start to i fails, so we move start to i + 1 and zero the tank.
• Because total gas ≥ total cost, the final start is guaranteed to complete the full circle.

Complexity

We use only two integers — no extra arrays or maps — so the space is O(1). The win is turning an O(n²) simulation into one O(n) pass by skipping entire failed stretches at once.

When this pattern shows up

Practice