Gas Station / Circular Tour

Problem. $n$ gas stations around a circle. Station $i$ has $\mathrm{gas}[i]$ fuel, and travelling from $i$ to $i+1$ costs $\mathrm{cost}[i]$. Starting with an empty tank, from which station can you complete the circuit?

The $O(n)$ greedy

int canCompleteCircuit(const vector<int>& gas, const vector<int>& cost) {
    long long total = 0, tank = 0;
    int start = 0;
    for (int i = 0; i < (int)gas.size(); i++) {
        long long diff = gas[i] - cost[i];
        total += diff;
        tank  += diff;
        if (tank < 0) { start = i + 1; tank = 0; }    // restart from the next station
    }
    return total >= 0 ? start : -1;
}

One pass, $O(1)$ space.

Why it works

Two claims.

1. A solution exists iff $\sum ({\mathrm{gas}}_i-{\mathrm{cost}}_i)\ge 0$. Necessity is clear. Sufficiency follows from claim 2.

2. If the tank goes negative while travelling from $s$ to $i$, then no station in $[s,i]$ can be the start. Suppose $j\in (s,i]$ were a valid start. Starting from $s$, the tank was non-negative on arrival at $j$ (otherwise we would have restarted earlier), so a run from $j$ has no more fuel than the run from $s$ had at $j$ — and that run failed by station $i$. So $j$ fails too.

Therefore restarting at $i+1$ never skips a valid answer, and one pass suffices. ∎

The structure is identical to Kadane’s reset rule: once the running total goes negative, discard the whole prefix.

The prefix-sum view

Let $d_i={\mathrm{gas}}_i-{\mathrm{cost}}_i$ and $P_k={\sum }_{i<k}{d}_i$. Starting at $s$ works iff every rotated prefix sum stays non-negative, which happens exactly when

$s=\arg {\min }_k{P}_k+1.$

So the valid start is just after the global minimum prefix, which is another way to see the same answer — and it generalises to “find all valid starts” (all positions achieving the minimum, when ties exist).

The general pattern: circular arrays

Technique	When
Duplicate the array ($2n$ length)	windows or subarrays that may wrap
Minimum prefix rotation	”find a starting point such that all prefixes are valid”
Total minus the complement	circular max subarray = $\max (\text{Kadane},\text{total}-\text{minSubarray})$
Fix one element in or out	circular DP; solve twice
Modular indexing	small circular scans

The gas station problem is the cleanest instance of the second row — and that reformulation (“which rotation makes all prefix sums non-negative”) appears in bracket-matching, in scheduling with deadlines, and in the cycle lemma.

The cycle lemma

For a sequence of integers $\ge -1$ summing to $k>0$, exactly $k$ of the $n$ rotations have all prefix sums positive.

For $k=1$ this says there is a unique valid rotation — which is why the gas station answer is unique when it exists, and it is also the combinatorial proof of the Catalan and ballot formulas.

Variants

Variant	Method
Find all valid starts	positions achieving the minimum prefix
Minimum starting fuel needed	$-{\min }_k{P}_k$
With a tank capacity limit	greedy fails; use a DP or a sliding window
Refuelling with a limited number of stops	greedy with a max-heap of passed stations
Non-circular (a straight road)	prefix sums with a running minimum
Multiple vehicles	a different problem entirely

Minimum refuelling stops

“Reach a target with a tank of size $T$, minimising stops.” Drive as far as possible; whenever you run out, retroactively refuel at the largest station passed so far (a max-heap). Greedy, $O(n\log n)$, and provably optimal by an exchange argument — the same “take everything, discard the worst” shape as job sequencing.

Why it is worth knowing

It teaches the prefix-sum reset argument: when a running total goes negative, the entire prefix can be discarded because nothing inside it can be a valid start. That one observation turns an $O(n^2)$ “try every start” into $O(n)$, and it recurs in Kadane, in bracket matching, and in circular scheduling.

See also: Kadane’s Algorithm · Prefix Sum · Exchange Arguments