Gas Station — Greedy One-Pass Circuit Feasibility [LC 134]

Problem Statement#

Given n gas stations in a circle, the i-th station provides gas[i] fuel and costs cost[i] to travel to the next station. Start with an empty tank and find the starting index from which you can complete the full circle, or return -1 if impossible. The answer is guaranteed unique when 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#

LeetCode 134 is a regular fixture at Amazon, Google, and Microsoft screens. The brute-force simulation — try every station, simulate the full circle — is O(n²) and times out at n = 10^5. The interviewer follow-up is always the same: "Can you do it in a single pass?" Candidates who can articulate the two key greedy insights — not just write the code — are the ones who advance.

The problem also teaches a transferable principle: whenever a circular array problem asks "does a valid starting point exist?", suspect a global feasibility check plus a linear greedy scan. The same structure reappears in Jump Game II, Minimum Refueling Stops, and Maximum Subarray (Kadane's algorithm). Investing time here pays dividends across an entire category of array interview questions.

The Core Insight#

Two insights combine into one elegant O(n) pass:

Insight 1 — Global feasibility: If sum(gas) < sum(cost), the circuit has a net fuel deficit. No starting station can overcome this. Return -1 immediately.

Insight 2 — Greedy elimination: Scan left to right, maintaining a running tank (net fuel from the current candidate start). When tank < 0, you cannot reach the next station from start. By a prefix-sum argument, every station between start and index i is also invalid — starting there gives an even worse running total. Reset start = i + 1, reset tank = 0, and continue.

Both accumulators update identically each step: total += net, tank += net. The difference is tank resets while total never does. After the full scan, return start if total >= 0, else -1.

Visual Dry Run#

gas = [1,2,3,4,5], cost = [3,4,5,1,2], net array = [-2,-2,-2,+3,+3]

total = 0 >= 0, return start = 3.

Solution (Optimal)#

class Solution:
    def canCompleteCircuit(self, gas, cost):
        total = 0
        tank = 0
        start = 0
        for i in range(len(gas)):
            net = gas[i] - cost[i]
            total += net
            tank += net
            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 net = gas[i] - cost[i];
        total += net;
        tank += net;
        if (tank < 0) {
            start = i + 1;
            tank = 0;
        }
    }
    return total >= 0 ? start : -1;
};

Time: O(n) — single pass through the array Space: O(1) — three scalar variables only

Common Mistakes#

• Returning -1 early when tank goes negative mid-scan — the global check determines impossibility, not local dips
• Forgetting to reset tank = 0 when resetting start — the new candidate starts with an empty tank
• Trying every station in a nested loop — O(n²) times out at n = 10^5
• Not justifying why stations between old start and i are safely skipped (prefix-sum elimination)
• Using modulo arithmetic unnecessarily — the linear scan plus global check avoids circular indexing

Interview Tips#

• State both insights before coding: global feasibility and greedy elimination
• Draw the net array gas[i] - cost[i] and explain that a non-negative total guarantees a solution
• Prove the reset: "Starting at any k where old_start < k <= i gives a prefix sum even more negative, so all eliminated"
• Connect to Kadane's algorithm — both use a running accumulator that resets when negative
• Mention the problem guarantees uniqueness, so the greedy always finds the correct one

Follow-up Questions#

• What if the answer is not guaranteed unique — how do you return all valid starting stations? (O(n²) or prefix-sum enumeration)
• How does this relate to Kadane's maximum subarray? (Identical reset mechanic, different semantic)
• What if you could refuel with different amounts mid-route? (Generalizes to min refueling stops with a max-heap)
• Can you solve it with streaming input (n unknown in advance)? (Maintain running totals, defer start decision)
• What if travel cost depends on both source and destination? (Graph shortest-path — greedy no longer applies)

Key Takeaways#

• LeetCode 134 is asked at Amazon, Google, and Microsoft; O(n²) brute force times out at n = 10^5
• If sum(gas) < sum(cost), return -1 — net deficit makes completion impossible regardless of start
• When running tank goes negative at index i, every station from current start through i is eliminated by prefix-sum proof
• Reset start = i + 1 and tank = 0; single linear pass finds the answer
• Complexity: O(n) time, O(1) space — two accumulators and one candidate index
• The greedy reset is structurally identical to Kadane's algorithm reset in Maximum Subarray
• Explaining the elimination proof separates strong candidates from those who merely memorized the code