Intermediate 3 min · March 24, 2026

Gas Station Problem — Why Greedy Fails With Dynamic Costs

Trucks ran out of fuel despite valid start.

Naren · Founder

Plain-English first. Then code. Then the interview question.

⚡Quick Answer

The gas station problem finds the unique start station for a circular tour when total gas ≥ total cost.
Key invariant: if you run out at station K starting from S, any station between S and K also fails.
Algorithm runs in O(n) time with O(1) space — single pass with two counters.
Performance: worst-case still O(n) — no hidden quadratic behavior.
Production insight: in real fuel logistics, this greedy assumption holds only if costs are static and station order fixed.
Biggest mistake: trying all start stations naively O(n^2) instead of using the greedy reset.

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.

Why the Greedy Works

Two key observations:

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.
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.

Edge cases to test

Single station: gas=[5], cost=[3] → start=0. gas=[3], cost=[5] → -1.
All stations have zero surplus: any start works (uniqueness broken only when total surplus exactly 0 at every prefix? Actually if all diffs are 0, every station works uniquely? No, if all zero, then starting at any station, you have 0 fuel at each step, so you complete. Multiple starts exist. But total surplus = 0. The uniqueness proof assumes that the cumulative surplus never goes negative; if it's always exactly zero, multiple starts can work. However that's a degenerate case. In production, handle by returning the first valid start (0) or any, per problem constraints.
Large positive surplus only at last station: e.g., gas=[0,0,10], cost=[1,1,1] → surplus = [-1,-1,9], total=7. Start should be 2.

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.

Algorithm Complexity Comparison

Approach	Time	Space	When to Use
Greedy (this)	O(n)	O(1)	Always fastest, but requires static costs
Brute Force (simulate each start)	O(n²)	O(1)	When n is small (< 1000) and code simplicity matters
DP with prefix sums	O(n)	O(n)	If you need to answer multiple queries for different start sets

Key Takeaways

If total gas ≥ total cost, exactly one valid starting station exists.
Track cumulative surplus; when it goes negative, reset start to next station.
O(n) time, O(1) space — single pass.
The greedy works because a failed start rules out all intermediate stations as potential starts.
Total surplus ≥ 0 is both necessary and sufficient for a solution to exist.

Common Mistakes to Avoid

Resetting start to i instead of i+1
Symptom: The algorithm returns the station that caused the negative surplus as the start, leading to infinite loop or wrong answer.
Fix: Change 'start = i' to 'start = i + 1'. The station that caused negative surplus cannot be a valid start.
Skipping the total surplus check and always returning start
Symptom: The algorithm returns a start even when no tour exists (e.g., gas=[1], cost=[2] returns 0 or 1 incorrectly).
Fix: Add 'if total_surplus < 0: return -1' before the return statement.
Using 'start = i + 1' but not resetting current_surplus to 0
Symptom: After reset, the algorithm accumulates previous negative surplus into the new start's calculation, causing false negatives.
Fix: After resetting start, always set current_surplus = 0. The two operations must be paired.

Interview Questions on This Topic

QWhy does resetting start to i+1 when surplus goes negative always give the correct answer?SeniorReveal
Because if you start at S and fail at K, any station between S and K would have even less fuel when reaching K (since the prefix from S to that station is non-negative, your surplus at that intermediate station is at least the surplus S had there). So they would also fail at K. Resetting to K+1 is safe: you've ruled out all stations up to K.
QProve that if total gas ≥ total cost, a valid starting station always exists.SeniorReveal
Think of the net gas array of size n. The cumulative sum from index 0 to any i is S(i). The total sum S(n-1) ≥ 0. Claim: there exists an index k such that the cumulative sum from k to i (wrapping) never goes negative. This is equivalent to finding a point where the prefix sum is minimal; if you start at the point after the global minimum, the cumulative sum never drops below zero. Formal proof: let m be the index where prefix sum is minimum (breaking ties arbitrarily). Then start = (m+1) % n works. The greedy algorithm finds this m because it resets at every negative prefix.
QWhat is the time and space complexity of the greedy gas station solution?JuniorReveal
Time: O(n) — exactly one pass through the array. Space: O(1) — only a few integer variables (total_surplus, current_surplus, start). No auxiliary data structures.
QCan there be more than one valid starting station? Why or why not?Mid-levelReveal
When total surplus > 0, the valid start is unique. Proof by contradiction: assume two distinct starts A and B. Starting from A, you reach B with non-negative surplus (since you haven't failed). From B, by definition you complete the circuit. Then you can start from A, go to B, and continue, returning to A with non-negative surplus. This implies the sum of surpluses from A to B (exclusive) is non-negative AND from B to A (exclusive) is also non-negative, adding to a positive total around the circle, contradicting that the total surplus is exactly the given sum (which is non-negative but could be zero). Actually, if total surplus = 0, multiple starts may exist if the cumulative surplus never goes negative from multiple starting points (degenerate zero array). But usually the problem expects uniqueness.
QHow would you modify the algorithm to return all valid starting stations?SeniorReveal
The standard greedy returns only one. To find all, we need to identify all indices where the cumulative surplus never goes negative when starting from that index. That's equivalent to finding all indices where the prefix sum (cyclic) is the global minimum. Compute circular prefix sums, find the minimum value, and collect all indices after that minimum. This runs in O(n) with O(n) space for the prefix array.

Frequently Asked Questions

Is there a case with exactly one valid start vs multiple valid starts?

When a solution exists, it is unique. If there were two valid starting stations, you could start from one, reach the other with positive fuel, continue the circuit, and return — implying surplus at both points, but that leads to a contradiction in the balance.

What happens if the total surplus is exactly zero?

Then exactly one start exists, unless all diffs are zero (then any start works). When total surplus = 0, the valid start is unique because any other start would require a negative cumulative segment somewhere.

Can this algorithm handle negative costs?

No, costs represent fuel needed; negative would mean gaining fuel by driving. That's physically unrealistic and breaks the problem constraints. If negative costs were allowed, the greedy invariant might fail.

🔥

That's Greedy & Backtracking. Mark it forged?

3 min read · try the examples if you haven't