Gas Station: Why Starting from the Failing Point Works (Greedy Proof)

Gas Station has one of the most counterintuitive greedy insights: if you can't reach station j from station i, start from station j+1.

This seems wrong at first. Why skip all stations between i and j? The proof is elegant and teaches you a powerful greedy pattern.

TL;DR

Greedy insight: If you can't reach station j from station i, you can't reach j from any station k where i < k < j.

Why? Balance from i to k must be non-negative (else we'd have failed earlier). If balance from i to j is negative, balance from k to j must also be negative.

Solution: Single pass, track cumulative balance, reset start when balance goes negative.

The Problem

LeetCode #134: Gas Station

Given gas and cost arrays, find starting station to complete circuit (or -1 if impossible).

Input: gas=[1,2,3,4,5], cost=[3,4,5,1,2]
Output: 3

Start at station 3:
  3→4: gas=4, cost=1, balance=+3
  4→0: gas=5, cost=2, balance=+3+3=+6
  0→1: gas=1, cost=3, balance=+6-2=+4
  1→2: gas=2, cost=4, balance=+4-2=+2
  2→3: gas=3, cost=5, balance=+2-2=0 ✓

The Greedy Solution

def canCompleteCircuit(gas, cost):
    total_tank = 0    # Total gas balance
    current_tank = 0  # Current gas balance
    start = 0         # Starting station
    
    for i in range(len(gas)):
        total_tank += gas[i] - cost[i]
        current_tank += gas[i] - cost[i]
        
        # Can't reach next station from current start
        if current_tank < 0:
            # Try starting from next station
            start = i + 1
            current_tank = 0
    
    # If total gas >= total cost, circuit is possible
    return start if total_tank >= 0 else -1

Time: O(n), Space: O(1)

Why Starting from Failing Point Works

The Claim

Claim: If you can't reach station j from station i, you can't reach j from any station k where i < k < j.

The Proof

Setup:

• Start at station i
• Fail to reach station j (cumulative balance becomes negative)
• Let balance(a, b) = cumulative gas balance from station a to station b

Given:

• balance(i, j) < 0 (we failed to reach j from i)

To prove:

• For any k where i < k < j: balance(k, j) < 0

Proof:

1. Since we reached station k from station i:

   • balance(i, k) ≥ 0 (else we'd have failed before k)

2. By definition of cumulative balance:

   • balance(i, j) = balance(i, k) + balance(k, j)

3. Rearranging:

   • balance(k, j) = balance(i, j) - balance(i, k)

4. Substituting known values:

   • balance(k, j) = (negative) - (non-negative)
   • balance(k, j) < 0 ✓

Conclusion: If we can't reach j from i, we can't reach j from any station between i and j. Therefore, next candidate is j+1.

Visual Proof

Stations: i ... k ... j

Balance from i to k: ≥ 0 (we reached k)
Balance from i to j: < 0 (we failed at j)

Balance from k to j = (i to j) - (i to k)
                    = (negative) - (non-negative)
                    = negative ✓

Therefore, can't reach j from k either.

Why Total Balance Determines Possibility

Claim: If total balance ≥ 0, circuit is possible. If total balance < 0, impossible.

Proof:

If total balance < 0:

• Total gas < total cost
• No matter where we start, we'll run out of gas
• Circuit is impossible ✓

If total balance ≥ 0:

• Total gas ≥ total cost
• There exists at least one starting point
• Our greedy algorithm finds it ✓

Why greedy finds it:

• If we fail at station j starting from i, we try j+1
• We've proven all stations between i and j also fail
• Eventually we find the valid starting point
• If no valid start exists, total balance would be negative

Example Trace

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

i=0: balance = 1-3 = -2 < 0
  Failed at station 1
  Next start: 1

i=1: balance = 2-4 = -2 < 0
  Failed at station 2
  Next start: 2

i=2: balance = 3-5 = -2 < 0
  Failed at station 3
  Next start: 3

i=3: balance = 4-1 = +3 ≥ 0
  Continue

i=4: balance = 3 + (5-2) = +6 ≥ 0
  Continue

Total balance = (1-3)+(2-4)+(3-5)+(4-1)+(5-2) = 3 ≥ 0
Circuit is possible, start = 3 ✓

Common Mistakes

Mistake 1: Not Resetting Current Tank

❌ Wrong:

if current_tank < 0:
    start = i + 1
    # Forgot to reset current_tank!

✅ Correct:

if current_tank < 0:
    start = i + 1
    current_tank = 0  # Reset balance

Mistake 2: Not Checking Total Balance

❌ Wrong:

return start  # What if circuit is impossible?

✅ Correct:

return start if total_tank >= 0 else -1

Conclusion

Gas Station teaches a powerful greedy insight: if you fail at position j, skip all positions before j.

Key proof: If balance from i to j is negative and balance from i to k is non-negative, then balance from k to j must be negative.

For more on greedy state tracking, see Greedy State Tracking and the complete greedy guide.