Gas Station Problem — Why Greedy Fails With Dynamic Costs

The gas station problem is LeetCode 134 and a canonical example of a greedy algorithm with a non-obvious correctness proof. The O(n) solution looks almost too simple — one pass, tracking two sums — but the proof of why it works is the important part.

The key insight, once you see it, is unforgettable: if you start at station S and fail at station K, then no station between S and K can be a valid starting point. They would all fail at K too, having less fuel at that point than S did. This single observation collapses what looks like an O(n^2) search into a single linear pass.

Why the Gas Station Problem Is a Greedy Trap

The gas station problem asks: given a circular route with n stations, each providing a certain amount of fuel and requiring a certain cost to travel to the next station, can you complete the circuit starting from some station? The classic version assumes static costs — each station's fuel and travel cost are fixed. But when costs vary dynamically — based on time, traffic, or demand — the greedy algorithm that works for the static case breaks completely.

In the static version, the key insight is that if total fuel >= total cost, a valid start exists, and you can find it in O(n) by tracking cumulative surplus and resetting when it goes negative. This works because costs are independent of the order of traversal. With dynamic costs, the cost to travel from station i to i+1 may change depending on when you arrive, breaking the monotonicity that makes the greedy solution correct.

You reach for this problem when modeling real-world logistics: delivery fleets, electric vehicle charging networks, or any system where a resource must be consumed in sequence and replenished at stops. In production, dynamic costs are the norm — traffic, energy prices, or battery degradation all introduce time dependence. The static greedy solution is a useful baseline, but you must validate that your costs are truly static before relying on it.

O(n) Greedy Solution

Key insight: if the total gas ≥ total cost, a solution always exists. To find it: track current tank. If tank goes negative, the current start is invalid — reset start to next station and reset tank.

def can_complete_circuit(gas: list[int], cost: list[int]) -> int:
    total_surplus = 0
    current_surplus = 0
    start = 0
    for i in range(len(gas)):
        diff = gas[i] - cost[i]
        total_surplus += diff
        current_surplus += diff
        if current_surplus < 0:
            # Can't start from any station 0..i
            start = i + 1
            current_surplus = 0
    return start if total_surplus >= 0 else -1

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

Why the Greedy Works

Two key observations:

1. If total gas ≥ total cost, a solution exists. The sum of all surpluses is non-negative, so there must be some starting point where cumulative sum never goes negative.
2. If starting from S, you run out at station k, then no station between S and k works as a start. Proof: if you could start from some S' between S and k, then starting from S (which has non-negative surplus from S to S') would also work from S' — but we know you run out at k. Contradiction. So S' is also invalid.

This means once we reset start to i+1, all previous starts are definitively ruled out.

Worked Example

gas = [1, 2, 3, 4, 5] cost = [3, 4, 5, 1, 2] diff = [-2,-2,-2, 3, 3]

i=0: surplus=-2 < 0 → start=1, surplus=0 i=1: surplus=-2 < 0 → start=2, surplus=0 i=2: surplus=-2 < 0 → start=3, surplus=0 i=3: surplus=+3 → start still 3 i=4: surplus=+3+3=6 → start still 3 total_surplus = -2-2-2+3+3 = 0 ≥ 0 → return start=3 ✓

Verify: start at 3 with 0 fuel. - Station 3: +4, -1 = 3 remaining. Drive to 4. - Station 4: +5, -2 = 6. Drive to 0. - Station 0: +1, -3 = 4. Drive to 1. - Station 1: +2, -4 = 2. Drive to 2. - Station 2: +3, -5 = 0. Back to start. ✓

Edge Cases and Uniqueness

When total surplus ≥ 0, exactly one starting station is valid. Proof: Suppose two valid starts, A and B. Starting from A, you reach B with non-negative surplus. From B, you can complete the circuit, so the total surplus from A to B plus B's circuit is … This leads to a contradiction because the sum of surpluses around the circle would be positive at two disjoint points.

Proof of Correctness (Detailed)

Lemma: If a circuit is possible (total surplus ≥ 0), the greedy algorithm returns a valid start.

Proof by induction on the number of resets. Base case: no reset → start=0 works because current_surplus never negative. Inductive step: Assume algorithm resets at station k. Then stations 0..k are ruled out. The problem reduces to finding start in subarray k+1..n-1 with total surplus unchanged (since total_surplus already accumulated from 0..k). By invariant, the remaining stations still have total surplus ≥ 0, so by induction a solution exists.

Thus O(n) correctness holds. The critical insight: a negative surplus at k means the cumulative sum from start to k is negative, so any earlier start would have even lower sum at k, confirming no valid start lies within.

The Naive Approach: Burning the Planet for a Test Drive

Most devs hit this problem and think: "Just try every station." That's the O(n²) solution — traverse the circle from each index until you either complete it or run dry. It works, you'll pass the interview, and your code will be slower than a memory leak on a Friday deploy.

Why is this bad? Because the problem is telling you something important: solution is unique. That means you're wasting time simulating loops that have zero chance of success. The naive approach checks each station independently, resetting the tank to zero like a rookie who doesn't read the logs.

You simulate a full circuit from station i. If you hit negative fuel at any point, you break and move to i+1. Circular indexing is handled with modulo. The tank starts at 0. If you survive n steps without going negative, you found your station. Otherwise, return -1.

This is fine for small inputs but will choke on the 10⁵ station test cases your platform will throw at you. The O(n²) cost is a bill that compounds. Let's look at the code so you can laugh at it before we move to the real solution.

// io.thecodeforge — dsa tutorial

public class GasStationNaive {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        
        for (int start = 0; start < n; start++) {
            int tank = 0;
            boolean possible = true;
            
            for (int steps = 0; steps < n; steps++) {
                int idx = (start + steps) % n;
                tank += gas[idx] - cost[idx];
                if (tank < 0) {
                    possible = false;
                    break;
                }
            }
            
            if (possible) return start;
        }
        
        return -1;
    }
}

The One-Pass Greedy: How to Skip Half the Work Without Guilt

Here's the trick that separates senior engineers from script kiddies: if you start at station 0 and run out of gas at station k, you can't start anywhere between 0 and k and succeed. Why? Because your tank was accumulating gas from every station before k. If you started later, you'd have even less gas at the bottleneck.

This is the insight that collapses O(n²) to O(n). You track total gas and total cost across the whole route. If total gas < total cost, return -1 immediately — you're never making it around the circle. If it's possible, you just need one pass to find where to start.

You keep a running tank balance and a candidate start index. Each time your tank goes negative, you reset the start to i+1 and your tank to 0. The algorithm feels like cheating. It is cheating. But it's mathematically sound and runs in one pass with constant space.

The key is trust. You don't re-check stations you've already proven can't work. That's the greedy mindset: make the locally optimal decision (reset here), and the global optimum falls out. This pattern appears in stock trading, interval scheduling, and a dozen other interview traps.

// io.thecodeforge — dsa tutorial

public class GasStationOnePass {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int totalGas = 0, totalCost = 0;
        int tank = 0, startIdx = 0;
        
        for (int i = 0; i < gas.length; i++) {
            totalGas += gas[i];
            totalCost += cost[i];
            tank += gas[i] - cost[i];
            
            if (tank < 0) {
                startIdx = i + 1;
                tank = 0;
            }
        }
        
        return totalGas >= totalCost ? startIdx : -1;
    }
}