Gas Station — LeetCode 134 One-Pass Greedy with Existence Proof

Problem Statement#

You have a circular route with n gas stations. At station i you gain gas[i] and the cost to travel to station i+1 is cost[i]. Return the starting index from which you can complete the loop, or -1 if impossible. The answer is unique if it exists.

Constraints:

• n == gas.length == cost.length
• 1 <= n <= 10^5
• 0 <= gas[i], cost[i] <= 10^4

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

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

Why This Problem Matters#

Gas Station is one of the all-time favorite greedy interview questions at Amazon, Uber, Google, and Goldman Sachs. The brute force is O(n^2) — try every starting station — but interviewers expect O(n). The leap to O(n) is the entire point of the problem.

The reason is the elegant existence argument: if total gas is at least total cost, a solution must exist; otherwise none does. Once you accept that, a single sweep produces the answer. The proof is a staple of FAANG behavioral evaluation: "explain why your algorithm is correct."

This pattern reappears in Maximum Subarray (Kadane), Minimum Size Subarray Sum, and Best Time to Buy/Sell Stock — any problem with a running-sum that resets on a negative state.

The Core Insight#

Run a tank starting at station 0. Add gas[i] - cost[i] each step. If the tank goes negative at index i, then no station from the previous start through i can be the answer (running tank only gets worse with more inclusions). Reset the start to i+1 and the tank to 0.

Existence: if total gas >= total cost, the loop is possible from some station. The greedy reset finds it. If total < total cost, return -1 directly.

Visual Dry Run#

Solution (Optimal)#

class Solution:
    def canCompleteCircuit(self, gas, cost):
        total = 0
        tank = 0
        start = 0
        for i in range(len(gas)):
            diff = gas[i] - cost[i]
            tank += diff
            total += diff
            if tank < 0:
                start = i + 1
                tank = 0
        return start if total >= 0 else -1

var canCompleteCircuit = function(gas, cost) {
    let total = 0, tank = 0, start = 0;
    for (let i = 0; i < gas.length; i++) {
        const diff = gas[i] - cost[i];
        tank += diff;
        total += diff;
        if (tank < 0) {
            start = i + 1;
            tank = 0;
        }
    }
    return total >= 0 ? start : -1;
};

Time: O(n) — one pass Space: O(1) — three integers

Common Mistakes#

• Resetting only tank and forgetting start = i + 1
• Returning the local start without checking total >= 0
• Computing total separately in a second pass — wasteful but not wrong
• Trying to wrap with modular arithmetic — unnecessary; the existence theorem handles it
• Using <= 0 instead of < 0 — a zero tank is fine to continue from

Interview Tips#

• Lead with the existence proof: "if total gas >= total cost, the answer exists"
• Explain the reset: "any failed start poisons every prefix, so skip past i"
• Mention this is the same template as Kadane and best-time-to-buy variants

Follow-up Questions#

• What if multiple valid starts exist? Hint: the problem guarantees uniqueness when total balances tightly
• What if you may stop and refuel from external sources? Hint: priority queue greedy (LC 871)
• What if cost[i] depends on tank level? Hint: DP on tank state
• How to find ALL valid starts? Hint: doubled-array sweep
• Online streaming version? Hint: sliding window with prefix sums

Key Takeaways#

• LeetCode 134 Gas Station is solved in O(n) with a one-pass greedy
• If total gas < total cost, no solution exists — return -1
• When tank dips below zero, skip the entire prefix and reset start to i+1
• Two accumulators are needed: tank (resettable) and total (cumulative)
• Existence argument: total nonneg implies some valid start
• Same reset pattern as Kadane and Maximum Subarray
• The answer is unique by problem guarantee, eliminating tie-breaking