Gas Station Circular Route, in depth: the skip lemma, the minimum-prefix-sum proof and when the greedy breaks

The problem, stated precisely

Define the gain of station i as g[i] = gas[i] - cost[i]: the net change in the tank when you fill up at i and drive to the next station. Starting at s with an empty tank, the tank after k legs is the sum g[s] + g[s+1] + ... + g[s+k-1], with indices taken mod n. Start s is valid when every one of those n partial sums is at least zero.

Three details of the statement are easy to get wrong:

• The tank is checked on arrival, after paying the cost of a leg. Arriving with exactly zero is allowed, because you refuel immediately at the station you just reached.
• The tank has no capacity limit. That assumption is what makes the gains additive, and the section on variants shows what happens without it.
• The answer need not be unique. LeetCode guarantees uniqueness for its tests, but in general several starts can be valid. A correct implementation returns one valid start, and a correct test checks validity, not a particular index.

Brute force, and why it is quadratic

The obvious solution tries every start and simulates the loop, which costs n legs per start:

def valid_start(gas, cost, s):
    n, tank = len(gas), 0
    for k in range(n):
        i = (s + k) % n
        tank += gas[i] - cost[i]
        if tank < 0:
            return False
    return True

def can_complete_brute(gas, cost):
    for s in range(len(gas)):
        if valid_start(gas, cost, s):
            return s
    return -1

That is O(n²) time. With n = 10⁵ it is ten billion leg updates, far too slow. Keep this function anyway: it is the oracle the fast version is tested against.

Two lemmas that make it linear

Two facts make a linear algorithm possible.

Lemma 1 (feasibility). If the total gain sum(g) is negative, no start is valid. A full loop uses every station exactly once, so the tank after n legs equals the total gain from any start. A negative total means that the final partial sum is negative wherever you begin.

Lemma 2 (skip). Suppose you start at s and the tank first goes negative after leaving station j. Then no station k with s < k ≤ j is a valid start either. Proof: you reached k from s with a tank of at least zero, so g[s] + ... + g[k-1] ≥ 0. The total g[s] + ... + g[j] is negative. Subtracting, g[k] + ... + g[j] is negative too. A car starting fresh at k has less fuel at j than the car that arrived at k carrying a surplus, and that car already ran dry.

Lemma 2 is the heart of the algorithm. One failed run from s eliminates every station from s to j, so the next candidate is j+1 and the scan never moves backwards. Every station is visited once.

The one-pass algorithm

Run one pass, keeping two sums. total accumulates every gain and decides feasibility at the end. tank holds the fuel since the current candidate start, and it is reset whenever it goes negative:

def can_complete_circuit(gas, cost):
    """Return a valid start index, or -1. O(n) time, O(1) extra space."""
    total = tank = 0
    start = 0
    for i in range(len(gas)):
        gain = gas[i] - cost[i]
        total += gain
        tank += gain
        if tank < 0:          # every start in [start, i] fails (skip lemma)
            start = i + 1
            tank = 0
    return start if total >= 0 else -1

The loop never wraps. That looks wrong at first, because the final candidate is never simulated past index n-1. The proof below shows why it does not need to be. The same code in Java should use long for the sums. With 10⁵ stations and gains up to 10⁴ in magnitude, the total stays below 2³¹, but production inputs carry no such bound.

static int canCompleteCircuit(int[] gas, int[] cost) {
    long total = 0, tank = 0;
    int start = 0;
    for (int i = 0; i < gas.length; i++) {
        long gain = (long) gas[i] - cost[i];
        total += gain;
        tank += gain;
        if (tank < 0) { start = i + 1; tank = 0; }
    }
    return total >= 0 ? start : -1;
}

The prefix-sum view

There is a second proof, and it explains why the loop does not need to wrap. Let P(0) = 0 and P(k) = g[0] + ... + g[k-1], so P(n) is the total. The tank after driving from s to position t is P(t) - P(s) when t > s, and P(n) - P(s) + P(t) after wrapping past the end. Start s is valid exactly when both kinds of value are non-negative for every t.

Choose s where P attains its minimum over k = 0..n-1. Then P(t) - P(s) ≥ 0 for every t, since nothing lies below the minimum. If the total P(n) is also non-negative, P(n) - P(s) + P(t) ≥ P(t) - P(s) ≥ 0 for the wrapped positions. So a minimum point is a valid start whenever the total is non-negative. Several indices can tie for the minimum, and each of them is valid, which is why answers are not unique in general.

The one-pass code computes this minimum. It resets exactly when P(i+1) falls strictly below P(start), so start always points at the first index that reached the lowest prefix seen so far. Reading the algorithm as "start at the deepest dip" gives a short alternative:

from itertools import accumulate

def start_at_min_prefix(gas, cost):
    P = [0, *accumulate(g - c for g, c in zip(gas, cost))]
    return P[:-1].index(min(P[:-1])) if P[-1] >= 0 else -1

Worked example

Take gas = [1, 2, 3, 4, 5] and cost = [3, 4, 5, 1, 2]. The gains are [-2, -2, -2, 3, 3], and their total is 0, so a valid start exists. The one-pass trace:

The total is 0, which is not negative, so the answer is 3. Check it by driving: start at 3 with an empty tank, fill 4 and burn 1 to arrive at 4 with 3. Fill 5 and burn 2 to reach 0 with 6. Fill 1 and burn 3 to reach 1 with 4. Fill 2 and burn 4 to reach 2 with 2. Fill 3 and burn 5 to arrive back at 3 with exactly 0. The car finishes on fumes, which the rules allow.

Now a case with ties: gas = [2, 0, 2, 0] and cost = [1, 1, 1, 1]. The gains alternate +1, -1, the prefixes are 0, 1, 0, 1, 0, and the minimum 0 occurs at k = 0 and k = 2. The algorithm never resets and returns 0, while the brute force would also accept 2. A test that hard-codes one index breaks the moment someone writes an equally correct implementation.

Testing against an oracle

Test with random small inputs, including zeros and negative-total cases, and compare the fast answer with the oracle by validity, not by index:

import random

def check(trials=20000):
    for _ in range(trials):
        n = random.randint(1, 8)
        gas = [random.randint(0, 5) for _ in range(n)]
        cost = [random.randint(0, 5) for _ in range(n)]
        got = can_complete_circuit(gas, cost)
        want = can_complete_brute(gas, cost)
        if want == -1:
            assert got == -1, (gas, cost, got)
        else:
            assert got != -1 and valid_start(gas, cost, got), (gas, cost, got)
    print("ok")

check()

Small n with small values hits the interesting cases often: an all-zero gain array, a total of exactly zero, a single station, and long runs of resets. Add explicit edge tests for n = 1 with gas equal to cost, which should return 0, and for n = 1 with gas below cost, which should return -1.

Common bugs

• Using ≤ 0 instead of < 0 for the reset. A zero tank is not a failure. Resetting on it moves the start forward needlessly, and when the zero lands on the last station it sets start to n: gas = [1], cost = [1] then returns 1, an index that does not exist. Reset only on a strictly negative tank.
• Checking feasibility with the final tank instead of the total. The tank covers only the segment since the last reset. A positive tank at the end says nothing about the stations before the start.
• Wrapping the loop twice "to be safe". Iterating 2n times with modular indices works, but it hides the proof and invites off-by-one bugs, such as returning a start of n or more.
• Integer overflow in fixed-width languages when sums are accumulated in 32-bit integers.
• Mismatched indexing of cost. Some statements charge cost[i] for the leg into station i rather than out of it. The leg out of i then costs cost[(i+1) % n], so gains must pair gas[i] with that value. Pairing gas[i] with cost[i] gives a different, wrong problem.

Variants where this greedy breaks

A finite tank breaks the greedy. With capacity C, the tank after a leg becomes min(C, tank + gas[i]) - cost[i]. Surplus fuel above C is lost, so gains are no longer additive, and the skip lemma fails: the car that reached k carrying fuel might have been capped, so it is not guaranteed to be better off than a fresh start at k. Fall back to per-start simulation, which is O(n²), or to more involved techniques when n is large. Do not reuse the one-pass code.

Choosing where to stop is a different problem. In LeetCode 871 (Minimum Number of Refueling Stops) the road is a line, stations sit at positions with fuel amounts, and you want the fewest stops to reach a target. The greedy there is different: drive as far as the tank allows, remember every station passed, and when you would run dry, retroactively refuel at the largest one passed so far.

import heapq

def min_refuel_stops(target, start_fuel, stations):
    """stations: list of (position, fuel), sorted by position."""
    heap, stops, fuel, i = [], 0, start_fuel, 0
    while fuel < target:
        while i < len(stations) and stations[i][0] <= fuel:
            heapq.heappush(heap, -stations[i][1])   # max-heap via negation
            i += 1
        if not heap:
            return -1
        fuel += -heapq.heappop(heap)
        stops += 1
    return stops

Both problems say "gas station" and both are greedy, but their correctness arguments share nothing. That is the general lesson: a greedy algorithm is only as good as the exchange or skip argument behind it, so prove the argument for the exact problem in front of you.

Trade-offs

What to do next

1. Implement both can_complete_circuit and the brute-force oracle, and run the randomized validity test until it passes 20,000 trials.
2. Write out the skip lemma proof in your own words, including why the car that reaches k carries a non-negative surplus.
3. Extend the prefix-sum version to return every index at the minimum, and confirm the tie example returns both 0 and 2.
4. Implement the capacity-limited variant by simulation, and find a small input where the one-pass greedy gives a wrong answer for it.
5. Solve minimum refueling stops with the heap, and note why its argument differs from this one.
6. Keep learning: greedy algorithms in general, activity selection and its exchange argument, the fractional knapsack, job scheduling with deadlines and Huffman coding.