LeetCode 134 – Gas Station

Gas Station is a greedy problem whose code is eight lines and whose proof is the entire interview. Anyone can write the loop after seeing it once; what is being tested is whether you can justify the two claims it rests on, because without them the algorithm is a guess that happens to be right.

The problem

n gas stations in a circle. Station i gives gas[i] fuel, and travelling from i to i+1 costs cost[i]. Starting with an empty tank, return the index you must start at to complete the circuit once, or -1 if it is impossible. The answer is guaranteed unique if it exists.

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

gas  = [2,3,4]
cost = [3,4,3]         -> -1

gas = [5], cost = [4]  -> 0
gas = [4], cost = [5]  -> -1

Work with the differences rather than the two arrays. delta[i] = gas[i] - cost[i] is the net fuel gained by making hop i, and the question becomes: is there a starting point from which every prefix sum around the circle stays non-negative?

delta = [-2, -2, -2, 3, 3]

starting at 3:  3, 6, 4, 2, 0   never negative  -> index 3 works

Claim 1: if the total is non-negative, an answer exists

Sum every delta. If it is negative, the trip consumes more fuel than exists and no start can work — that direction is obvious.

The other direction is the useful one: if the total is non-negative, some start succeeds. Take the station where the running prefix sum is at its lowest point over the whole circle, and start at the one after it. Every partial sum measured from there is the original prefix sum minus that minimum, so none of them can be negative — and the wrap-around portion is covered by the total being non-negative.

That is worth saying in one sentence out loud. It is what converts "check the total" from a plausible heuristic into a decision procedure.

Claim 2: a failure lets you skip everything you have covered

Suppose you start at s and run dry on the hop leaving station i. Then no station in s … i can be a valid start.

Why: because you reached each of those stations with a tank that was non-negative at the time. Starting at any of them instead means arriving with zero rather than with that surplus — strictly no better. If the surplus was not enough to get past i, nothing less will be either.

start at s, run dry leaving i
  -> s, s+1, ..., i are all ruled out at once
  -> next candidate is i + 1

This is what makes the algorithm one pass instead of O(n²). Each failure eliminates an entire block of candidates rather than one, so the start pointer only ever moves forward.

Java

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int total = 0;    // sum of all deltas: decides whether ANY answer exists
        int tank = 0;     // fuel since the current candidate start
        int start = 0;

        for (int i = 0; i < gas.length; i++) {
            int delta = gas[i] - cost[i];
            total += delta;
            tank += delta;

            if (tank < 0) {
                // Nothing in start..i can work, so jump the whole block.
                start = i + 1;
                tank = 0;
            }
        }

        return total < 0 ? -1 : start;
    }
}

Two accumulators that look similar and are not. total never resets and answers "does a solution exist at all"; tank resets on every failure and tracks the current candidate. Collapsing them into one variable is the classic way to break this.

There is no second lap and no modular arithmetic. The single forward pass is sufficient because of the two claims — which is why they are worth stating before the code rather than after.

Python

class Solution:
    def canCompleteCircuit(self, gas: list[int], cost: list[int]) -> int:
        total = tank = start = 0

        for i, (g, c) in enumerate(zip(gas, cost)):
            delta = g - c
            total += delta
            tank += delta

            if tank < 0:                 # start..i all ruled out
                start = i + 1
                tank = 0

        return start if total >= 0 else -1

When total < 0, start may have been left at len(gas) — an out-of-range index. It is never returned, because the total check happens first, but it is worth noticing rather than discovering: returning start unconditionally would hand back an invalid index on every impossible input.

Complexity

The brute force is a perfectly good first answer and passes on small inputs. Offering it, then deriving the two claims that collapse it to one pass, is a much better interview than jumping to the final loop.

The pattern

"Reset the accumulator when it goes negative" is Kadane's algorithm — there a negative running sum means "drop the prefix", here it means "drop every candidate start in the prefix". The same move, read two ways, and the connection is worth naming.

The circular structure also recurs: Maximum Sum Circular Subarray (918) handles wrap-around by running Kadane twice, and the trick of taking the total minus the worst stretch is the same reframing as Claim 1 here.

What the interviewer is checking

• That you reduce two arrays to one array of deltas.
• That you can justify why a non-negative total guarantees a solution.
• That you can justify skipping the whole block after a failure — the real insight.
• That total and tank stay separate variables.
• The impossible case returning -1, and not a stale index.
• Single-station inputs both ways.
• That you connect the reset to Kadane rather than treating it as a trick.