Gas Station

1. Problem & Core Objective

There are n gas stations arranged in a circle. Station i has gas[i] fuel, and it costs cost[i] to travel from station i to station i+1. You start with an empty tank at some station and must complete the full loop. Return a valid starting index, or -1.

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

Constraints: 1 <= n <= 10^5, 0 <= gas[i], cost[i] <= 10^4. LeetCode adds: if a solution exists, it is unique.

What's actually being tested: whether you can prove a block of candidates dead at once. Trying each start independently is O(n²); the linear solution rests on one argument — a failure at station i disqualifies every start from the current one through i, not just the current one. Everything else is bookkeeping.

2. First-Principles Thought Process

Collapse two arrays into one

Only the difference ever matters:

diff[i] = gas[i] - cost[i]

Now the question is: is there a rotation of diff whose every prefix sum is non-negative? Two arrays became one, and a physical story became a statement about prefix sums.

Feasibility is a one-line check

Over a full loop every station is visited exactly once, so the tank ends at sum(diff) regardless of where you start. If that total is negative, no start can work — you're consuming more fuel than exists.

And the converse holds: if sum(diff) >= 0, some start works. The proof is the "lowest point" argument. Let P(k) be the prefix sum after k steps from index 0, and let m be the index where P is minimum. Start at m + 1. Every subsequent prefix, measured from there, is P(k) − P(m) >= 0 by the definition of the minimum — and after wrapping, the total surplus keeps it non-negative too.

So feasibility is decided entirely by the sum, and the only remaining job is finding the start.

The reset argument — the part that matters

Sweep with a running tank from a candidate start. If the tank goes negative on arriving at station i, three things are true:

1. start fails. Obvious.
2. Every station s strictly between start and i also fails. This is the real content.
3. So the next candidate is i + 1, and nothing between needs testing.

Why (2) holds: because the tank never went negative before i, every prefix sum(start..s-1) is >= 0. Therefore

sum(s..i) = sum(start..i) − sum(start..s−1)  ≤  sum(start..i)  <  0

Starting later means discarding a non-negative prefix, which can only leave you with less fuel on arrival at i. So s fails too.

That is the identical shape of argument as Kadane's — a non-negative prefix is never worth dropping; a negative one is never worth keeping — applied to a feasibility question instead of an optimisation.

Why one pass suffices even though it's a circle

The loop only ever scans indices 0..n-1 once, never wrapping. That looks suspicious for a circular problem, and the justification is:

• If the total is negative, the answer is −1 regardless of what the sweep found.
• If the total is non-negative, the sweep's final start is correct, because every index before it has been proved infeasible, and feasibility guarantees at least one index works. Only one candidate remains standing.

The circularity is handled by the total check, not by the scan. Saying that explicitly is the cleanest way to defuse "but you never wrapped around".

About that uniqueness guarantee

LeetCode states the answer is unique when it exists. That is a promise about their test data, not a theorem — and it's worth knowing the difference.

Measured on 4,000 random (gas, cost) pairs: 1,709 had more than one valid start, and 1,595 of those had a strictly positive total surplus. For example gas = [0,0,0,3,4,4], cost = [3,1,0,1,4,0] admits four valid starting stations. Surplus fuel makes multiple rotations survivable; uniqueness essentially requires the total to be exactly 0.

Two consequences worth knowing:

• The reset version below returns the smallest valid start — verified on 212,882 feasible random inputs with no exceptions.
• The prefix-minimum version returns a different valid start in 90,335 of those same cases. Both pass LeetCode; only one would pass a test that pinned the expected index.

3. Solution Paths

Approach 1 — Brute force, simulate every start

public int canCompleteCircuit(int[] gas, int[] cost) {
    int n = gas.length;
    for (int s = 0; s < n; s++) {
        int tank = 0;
        boolean ok = true;
        for (int k = 0; k < n; k++) {
            int i = (s + k) % n;                 // modular index = the circle
            tank += gas[i] - cost[i];
            if (tank < 0) { ok = false; break; }
        }
        if (ok) return s;
    }
    return -1;
}

• Time O(n²) · Space O(1)

Counter-questions on this approach

⭐ "How does the modular index handle the wrap?"

(s + k) % n walks n stations starting from s, wrapping past the end. The alternative is to physically concatenate the array with itself and index s..s+n-1, which trades O(n) space for avoiding the %.

Both are standard for circular arrays; the doubled array is usually clearer when you also need subarrays of the rotation, and the modulus is better when you just need a walk.

"Where does the break leave you, and is that information wasted?"

It leaves you knowing that s fails at station i. This version throws that away and restarts at s + 1 — and the whole optimisation is realising the failure index tells you s+1 .. i are dead too.

That's the bridge I'd build out loud rather than jumping straight to the linear code.

"What's the actual cost at the constraint limit?"

10^5 squared is 10^10 — several minutes. Not borderline; genuinely infeasible.

Approach 2 — Prefix sums, find the minimum

public int canCompleteCircuit(int[] gas, int[] cost) {
    int n = gas.length, total = 0, minPrefix = Integer.MAX_VALUE, minIndex = -1;
    for (int i = 0; i < n; i++) {
        total += gas[i] - cost[i];
        if (total < minPrefix) { minPrefix = total; minIndex = i; }
    }
    return total < 0 ? -1 : (minIndex + 1) % n;
}

• Time O(n) · Space O(1)

This is the constructive version of the feasibility proof: start immediately after the lowest point of the prefix-sum curve.

Counter-questions on this approach

⭐ "Why is 'just after the minimum prefix' the right start?"

Because from that point every prefix sum, re-based, is P(k) − P(min) >= 0 by definition of the minimum. The lowest point of the fuel curve is exactly where you want your tank to be empty — start there and you never dip below zero.

It's the same reasoning as "maximum drawdown" in a time series: shift the origin to the trough.

"Why (minIndex + 1) % n?"

If the minimum prefix falls at the last index, the start wraps to 0. gas = [2,1], cost = [1,2] is the smallest case: diff = [1, -1], prefix sums [1, 0], so the minimum is at index 1 and the correct start is (1 + 1) % 2 = 0. Without the modulus you'd index out of bounds.

⭐ "Does this return the same index as the reset version?"

Often not. Both are valid starts, but they're different ones whenever the answer isn't unique. Measured over 212,882 feasible random inputs: the two agree on only 122,547 — about 58%. The smallest disagreement I found is diff = [0, 1, 4, 4], where the reset version returns 0 and this one returns 1; both complete the loop.

More precisely: the reset version returned the smallest valid start in all 212,882 cases, and this one did not in 90,335 of them. That difference is invisible on LeetCode only because their data guarantees a unique answer.

"Is this better or worse than the reset version?"

Same complexity, and arguably easier to prove — the trough argument is one line. The reset version is easier to derive from the brute force, and it's the one that shows you understand why candidates can be eliminated in blocks.

I'd write the reset version and mention this one as the proof of why a solution must exist.

Approach 3 — One pass with a reset (optimal)

public int canCompleteCircuit(int[] gas, int[] cost) {
    int total = 0, tank = 0, start = 0;
    for (int i = 0; i < gas.length; i++) {
        int diff = gas[i] - cost[i];
        total += diff;
        tank  += diff;
        if (tank < 0) {                  // can't reach i+1 from `start`...
            start = i + 1;               // ...and no station in [start, i] can either
            tank  = 0;
        }
    }
    return total < 0 ? -1 : start;
}

• Time O(n) · Space O(1)

Counter-questions on this approach

⭐ "You never wrap around. Why is the answer still valid for a circle?"

Two separate facts do the work. The sweep eliminates candidates: every index before the final start has been proved infeasible by the reset argument. The total check guarantees existence: if sum(diff) >= 0 some rotation works. Together, the one survivor must be it.

The circle is handled by the existence proof, not by the traversal. If I only had the sweep I really would need to wrap.

⭐ "Prove the reset skips over only dead candidates."

Suppose the tank first goes negative on arriving at i, having started at start. For any s in (start, i], the prefix sum(start..s−1) is non-negative — otherwise the reset would have fired earlier. Then

sum(s..i) = sum(start..i) − sum(start..s−1) ≤ sum(start..i) < 0

so s also runs dry at or before i. Every skipped index is genuinely dead.

"Why are total and tank both needed — aren't they the same sum?"

They diverge at every reset. total accumulates the whole array unconditionally and answers "does any solution exist?". tank is reset to 0 and answers "is the current candidate still alive?".

Collapsing them into one variable is the classic bug: you'd lose either the feasibility test or the candidate test.

"Could you return early once start stops moving?"

No — you can't know it has stopped without finishing, and you still need total over the entire array. This function has no early exit, which is a small point worth making because most greedy sweeps do.

"Is tank = 0 right, or should it carry the deficit forward?"

It must be 0. The next candidate starts with an empty tank, not a debt. Carrying the negative value forward would conflate a failed run with the fresh one and could push start past a valid station.

4. Why the Optimal Solution Wins

Both linear versions are optimal and neither can be improved — every station must be read.

Write the reset version, because the interview value is in the sentence "a failure at i kills every candidate back to start, not just start". Keep the minimum-prefix version in reserve as the answer to "how do you know a solution exists at all?"

5. Java Prerequisites

Two accumulators with different reset policies

total += diff;      // never reset — global feasibility
tank  += diff;      // reset to 0 on failure — candidate viability

The single most important line in the function is the one that doesn't reset.

Circular indexing

int i = (s + k) % n;                        // modulus
// or: iterate 0..2n-1 over a doubled array and index % n

Summing an array

int total = Arrays.stream(gas).sum() - Arrays.stream(cost).sum();

Readable for the feasibility precheck, but it's a second and third pass. The single-loop version accumulates total alongside tank for free.

Overflow

10^5 stations at 10^4 each caps total at 10^9, inside int — but with under one bit of headroom. If either constraint grew, long.

6. Interview Communication Guide

Clarifying questions: Is the tank capacity unlimited (yes)? Must I return the index or just whether one exists (the index)? Is the answer guaranteed unique (LeetCode says so — I'd note that's a property of the test data, not of the problem)? Can gas[i] or cost[i] be zero (yes)?

The pitch

"First I'd collapse the two arrays into one: diff[i] = gas[i] − cost[i]. The question becomes whether some rotation of diff has all non-negative prefix sums.

That immediately gives the feasibility test. Over a full loop you consume every station exactly once, so the final tank is sum(diff) no matter where you start — negative total means no start works. And the converse holds too: if the total is non-negative, starting just after the lowest point of the prefix-sum curve works, because every prefix measured from there is at least zero by definition of the minimum.

So a solution exists iff the total is non-negative, and I just need to find it.

For that I sweep once with a running tank. When the tank goes negative arriving at station i, I don't just discard the current start — I discard every station from the current start through i. The reason: each of those was reached with a non-negative tank, so starting there means throwing away a non-negative prefix, and you'd arrive at i with even less. That's what turns O(n²) into one pass.

I'd point out that the scan never wraps around, which looks wrong for a circular problem. It's fine because the two halves do different jobs — the sweep eliminates candidates, and the total check guarantees one survives. Neither alone would be enough.

O(n) time, O(1) space, and it needs both accumulators: total never resets, tank does."

Edge cases to volunteer:

Name gas=[2,3,4], cost=[3,4,3]. The sweep alone would hand back start = 2 there, and only the total < 0 check turns it into −1. It's the input that proves the two accumulators aren't redundant.

7. Follow-Up Questions — Modified Constraints

⭐ "Return all valid starting stations, not just one."

Compute the prefix sums once, then every index i such that P(i) == min(P) yields a valid start at i + 1. That's O(n) and returns them all.

Worth pairing with the measurement: multiple valid starts are the common case, not the exception — 1,709 of 4,000 random inputs had more than one, and the two standard O(n) solutions disagree about which to report roughly 42% of the time. The "unique answer" phrasing on LeetCode hides both facts.

⭐ "What if the tank had a maximum capacity C?"

The reset argument breaks. Its proof relies on "starting later means carrying less fuel", which is only true when fuel accumulates without bound — with a cap, a later start can arrive at i with the same fuel as an earlier one, so the elimination is no longer valid.

You'd fall back to simulating each start, O(n²), or to a sliding-window feasibility check. This is my favourite follow-up here because it shows exactly which assumption the linear solution is standing on.

"What if you could travel in either direction?"

Run the same algorithm on the reversed problem — going backwards from i to i−1 costs cost[i−1] and collects gas[i]. Two independent O(n) sweeps, take whichever succeeds. Direction changes mid-loop would make it a different problem entirely, since you could revisit stations.

"What if you start with k units of fuel already in the tank?"

Feasibility becomes total + k >= 0, and the trough start is still correct — starting just after the minimum prefix, the deepest dip over the whole loop is min(0, total), so k units of slack cover exactly the case total < 0. Verified: total + k >= 0 matched brute-force feasibility on all 8,000 test inputs, with no mismatches.

The reset version is the one that gets shaky. Its elimination proof needs sum(start..s−1) >= 0; with a starting reserve the sweep only guarantees >= −k, so skipped candidates are no longer provably dead. Measured: with k > 0 the sweep skipped over a genuinely valid earlier start in 14,450 of 297,538 feasible cases — it never does this at k = 0.

It still returned a valid start every time (0 failures in 297,538), so the algorithm survives; what's lost is the guarantee that it finds the earliest one. If I needed the earliest, I'd use the prefix-minimum version.

"Stations in a line rather than a circle?"

Much easier — you'd just check whether starting at 0 works, since there's no rotation to choose. The circle is the entire difficulty.

"What if n were 10^7 and the values 10^9?"

Switch total and tank to long — 10^7 × 10^9 = 10^16 overflows int by six orders of magnitude. The algorithm is otherwise unchanged; it's already one pass with two variables.

"Can you do this in parallel?"

Yes, via the prefix-sum formulation: prefix sums are a parallel scan, and "index of the minimum" is a parallel reduction. Both are O(log n) depth. The reset formulation is inherently sequential, which is a genuine reason to prefer the other one at scale.