Gas Station Problem: Why the One-Pass Greedy Works

The gas station problem has a solution that fits in six lines and looks like a guess: sweep once, and whenever the tank goes negative, jump the starting point forward. Most people can write it after seeing it once. Far fewer can say why it is allowed to skip every station in between — and that argument is what the question is really about.

The problem it solves

There are n stations on a circular road. Station i gives you gas[i] litres, and driving from station i to the next one costs cost[i]. You start with an empty tank at a station of your choice. Return a starting index from which you can drive the whole loop once, or -1 if none exists.

Trying every start and simulating the loop is O(n²). The greedy answer is O(n) time and O(1) memory.

The intuition

Only the difference matters at each station, so write net[i] = gas[i] - cost[i]. The tank after a stretch of stations is just the sum of their net values.

Two facts carry the whole solution.

Fact 1: a loop exists if and only if the total of net is at least zero. If the total is negative, no ordering of the same stations can end with fuel to spare, so every start fails. The other direction — a non-negative total guarantees some start works — follows from fact 2.

Fact 2: if you start at s and run dry just before station i + 1, then no station from s to i can be the start. Take any station m in between. Starting at s, you arrived at m with a tank of zero or more, because you had not yet run dry. Starting fresh at m means arriving with exactly zero — never more than before. From m to i you add the same net values either way, so if the tank went negative with the head start, it goes negative without it.

So when the tank goes negative at i, the next candidate is i + 1, and the stations skipped are provably useless. The sweep ends with one surviving candidate, and a prefix-sum picture shows why it works when the total is non-negative.

Plot the running sum of net from station 0. Every reset happens where that curve reaches a new low, so the survivor sits right after its lowest point. Starting there, the curve never drops back below that low for the rest of the array, so the tank never goes negative before the wrap. After the wrap, the tank at any earlier station equals the whole stretch to the end plus that station's prefix sum — and since no prefix is below the lowest one, that is at least the grand total, which is at least zero. That is why the code returns the survivor without a second loop.

Watch it run

The animation uses the lesson's five stations, with net values -2, -2, -2, +3, +3. Starting at 0 fails immediately, so the candidate moves to 1, then 2, and each failure rules out the stretch behind it. From station 3 the tank climbs to 3 and then 6, and the grand total closes at exactly zero. One pass, and the answer is 3.

The code

The sweep keeps two totals because it answers two questions at once: total decides whether any start can work, tank tests the current candidate.

def can_complete(gas, cost):
    total = tank = start = 0
    for i in range(len(gas)):
        step = gas[i] - cost[i]
        total += step                  # can ANY start make the loop?
        tank += step                   # can THIS start reach station i + 1?
        if tank < 0:
            start, tank = i + 1, 0     # every candidate up to i is ruled out
    return start if total >= 0 else -1

def brute(gas, cost):                  # try every start, drive the full loop
    n = len(gas)
    for s in range(n):
        tank = 0
        for k in range(n):
            i = (s + k) % n
            tank += gas[i] - cost[i]
            if tank < 0:
                break
        else:
            return s
    return -1

print(can_complete([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]))   # 3
print(can_complete([2, 3, 4], [3, 4, 3]))               # -1
print(can_complete([4, 1, 1], [1, 2, 3]))               # 0

The brute force simulates every start around the full circle and returns the first one that never runs dry. The two are compared on 20,000 random inputs, with small values so that zero tanks, ties and impossible loops all come up often:

import random
random.seed(8)
ok, solvable = True, 0
for _ in range(20000):
    n = random.randint(1, 9)
    gas = [random.randint(0, 6) for _ in range(n)]
    cost = [random.randint(0, 6) for _ in range(n)]
    ok &= can_complete(gas, cost) == brute(gas, cost)
    solvable += brute(gas, cost) != -1
print(ok, solvable)                    # True 10800

They agree on all 20,000, of which 10,800 had a valid start. Notice that they agree even when several starts work: the greedy sweep returns the smallest valid index. That follows from fact 2 — a candidate that reaches a valid start is never pushed past it, because a valid start never runs dry.

The complexity

One pass over the stations with three integers of state: O(n) time and O(1) extra memory. The brute force is O(n²), because each of n starts may drive nearly n legs before failing.

Where it goes wrong

• Resetting to i instead of i + 1. Station i is where the tank went negative, so it is inside the failed stretch and is itself ruled out.
• Checking only tank at the end. The final tank covers only the stretch from the last candidate to the end of the array. Without total, an impossible input returns a start that fails halfway round.
• Using > instead of >=. A total of exactly zero is a valid loop that finishes with an empty tank, as in the animation's example.
• Assuming the answer is unique. Many statements promise a unique solution. If yours does not, say that the sweep returns the smallest valid start, and check that is what is wanted.

How to say it in an interview

"If total gas is less than total cost, no start works. Otherwise I sweep once with a running tank from a candidate start. When the tank goes negative at station i, every station from the candidate to i fails too, because each of them would be reached with at least as much fuel from the candidate as from a fresh start, so I move the candidate to i + 1 and reset. The survivor is the answer — O(n) time, O(1) space."

The same "a failed prefix rules out everything inside it" shape appears in Kadane's algorithm, where a negative running sum is dropped rather than carried forward.