Gas Station
Problem
0..n-1 sit on a circular road. At station i you
may fill up gas[i] units, and driving on to station i+1 burns
cost[i] units. Starting with an empty tank, return the station from which you
can drive one full lap clockwise, or -1 if none exists (the answer is unique
when it exists).gas=[1,2,3,4,5] cost=[3,4,5,1,2]Output3gas=[2,3,4] cost=[3,4,3]Output-11 ≤ n ≤ 105 · 0 ≤ gas[i], cost[i] ≤ 104 · answer is unique if it exists
Try it yourself
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
}
}
j when starting from
s, then no station between s and j can start either (each arrives there
with ≥ 0 fuel, which only helps). And a lap is possible iff
Σgas ≥ Σcost.Instinct An optimisation where one obvious local rule (earliest end, farthest reach, biggest first) never needs undoing - commit to it, then try hard to break it.
Memory hack Grab the best bite now and never look back - but only once a counterexample hunt fails to make you regret it.
Open the Greedy guide →Approaches
Brute ForceSimulate from Every Station
O(n2)Space O(1)Try each start and drive n legs, adding
gas[i] - cost[i] to the tank; abandon the start as soon as the tank
drops below zero. The first start that survives all legs is the answer.
public int canCompleteCircuit(int[] gas, int[] cost) { int n = gas.length; for (int start = 0; start < n; start++) { int tank = 0, legs = 0; while (legs < n) { int i = (start + legs) % n; tank += gas[i] - cost[i]; if (tank < 0) break; legs++; } if (legs == n) return start; } return -1; }
Direct translation of the statement, but quadratic for n = 105.
BetterSimulation with Skip-Ahead
O(n)Space O(1)Same simulation, but when a start s fails at station
j, jump straight to j + 1 — the key insight rules out
everything in between. Each station is driven through at most twice (once more on
the final wrap-around lap).
public int canCompleteCircuit(int[] gas, int[] cost) { int n = gas.length; int start = 0; while (start < n) { int tank = 0, legs = 0; while (legs < n) { int i = (start + legs) % n; tank += gas[i] - cost[i]; if (tank < 0) break; legs++; } if (legs == n) return start; start += legs + 1; // starts in [start, start+legs] all fail } return -1; }
Linear, but up to 2n steps and fiddly modular indexing.
OptimalOne-Pass Greedy (Total + Running Surplus)
O(n)Space O(1)Scan once. total sums every gas[i] - cost[i];
tank is the surplus since the current candidate. When tank
goes negative, the candidate becomes i + 1 and tank resets.
If total ≥ 0, the surviving candidate covers the stations before it
too, so it completes the lap.
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; tank = 0; } } return total >= 0 ? start : -1; }
Dry rundiff = gas - cost = [-2,-2,-2,3,3]
- i=0-2i-2s-233tank=-2 < 0 → start=1
- i=1-2-2i-2s33tank=-2 → start=2
- i=2-2-2-2i3s3tank=-2 → start=3
- i=3-2-2-23i s3tank=3
- i=4-2-2-23s3itank=6, total=0 → 3 ✔
Single pass, no wrap-around simulation — the standard answer.
diff — the same idea seen another way.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Simulate from Every Station | O(n2) | O(1) |
| Better | Simulation with Skip-Ahead | O(n) | O(1) |
| Optimal | One-Pass Greedy (Total + Running Surplus) | O(n) | O(1) |
- Resetting
start = iinstead ofi + 1— station i itself just failed. - Skipping the
total ≥ 0check — returns a start even when no lap is possible. - Forgetting the wrap-around (
% n) in the simulation versions.
- Prove both lemmas aloud: the skip-ahead argument and the total-sum feasibility test.
- Work with
diff[i] = gas[i] - cost[i]; the problem becomes a prefix-sum one. - Mention that the unique-answer guarantee is why the first surviving start is enough.