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.

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.

Frequently Asked Questions