Gas Station

Gas Station is the standard example of a greedy that looks impossible at first. There are n possible starting stations and each needs a full trip to check, so the obvious answer is O(n²). Two short facts turn it into one pass, and each has a proof you can say in a sentence.

It is also a prefix-sum problem in disguise. Once you draw the running fuel total as a line, the answer is simply the point right after its lowest dip.

The problem

Stations sit on a circular road, numbered 0 to n − 1. At station i you can fill up gas[i] litres, and driving from station i to the next one (station n − 1 leads back to 0) burns cost[i] litres. Your tank starts empty and has no limit. Return the station where you should start to drive once all the way round, or −1 if no start works. When an answer exists, it is unique.

• gas = [4, 1, 3, 1, 5], cost = [2, 4, 2, 3, 2] → 4. From station 4 the tank reads 3 on arrival at 0, then 5, 2, 3, 1 on arrival back at 4 — never negative.
• gas = [3, 1, 2], cost = [2, 3, 2] → −1. The road needs 7 litres in total and the stations hold only 6.

Constraints: 1 ≤ n ≤ 10⁵, and every value is between 0 and 10⁴.

Clarifying questions

• Do you fill up at the start station before leaving? Yes, the first move is fill then drive.
• Is reaching a station with exactly 0 left fine? Yes; only negative is a failure.
• Can there be several valid starts? No, the problem guarantees uniqueness — but the algorithm still returns a valid one if there were.
• Return the index or a boolean? The index, or −1.

Approach 1: the simple way

Try every start and simulate the trip.

1def start_station_brute(gas: list[int], cost: list[int]) -> int:2    """Try every start and drive the whole loop."""3    n = len(gas)4    for start in range(n):5        tank = 06        for step in range(n):7            i = (start + step) % n8            tank += gas[i] - cost[i]9            if tank < 0:10                break11        else:12            return start13    return -1

(The else on a for loop runs only when the loop did not break — here, when the whole lap succeeded.)

This is O(n²) time and O(1) space. With n = 10⁵ that is up to 10¹⁰ steps. And most of the work is repeated: a failed trip from station 0 drives past stations 1, 2 and 3, then the next attempt drives the same road again from station 1.

The key insight

Work with the net gain at each station, gas[i] − cost[i]. For the example that is [+2, −3, +1, −2, +3]. Two facts do all the work.

Fact 1 — a start exists if and only if the total gain is at least 0. If the stations hold less fuel than the road needs, no start can work. The other direction is the surprising part, and it is proved below.

Fact 2 — if you start at a and first run dry on the way out of station b, then no station from a to b can be the answer. Take any station c between them. When your trip from a passed c, the tank was at least 0 — the trip had not failed yet. Starting fresh at c means arriving with exactly 0, which is no better. So from c you run dry at b too, or earlier. The next candidate is b + 1, not a + 1.

Fact 2 is the greedy step. You never retry a start you have ruled out, so each station is visited once.

Why the last candidate works all the way round. Let the running total be P: P(0) = 0 and P(i + 1) = P(i) + gain[i]. For the example, P = [0, 2, −1, 0, −2, 1]. Pick the start s right after the lowest value of P — here P(4) = −2, so s = 4. Your tank on arriving at a station j after s is P(j) − P(s), which is never negative because P(s) is the lowest. After you wrap past the end, the tank is P(n) − P(s) + P(j): that is the total (at least 0 by Fact 1) plus P(j) − P(s) (at least 0 again). Never negative. That also proves Fact 1.

Approach 2: optimised — reset when the tank goes negative

1def start_station(gas: list[int], cost: list[int]) -> int:2    """One pass: restart after any station where the tank goes negative."""3    if sum(gas) < sum(cost):4        return -1                      # not enough fuel in total5    start, tank = 0, 06    for i in range(len(gas)):7        tank += gas[i] - cost[i]8        if tank < 0:                   # start..i are all bad starts9            start = i + 110            tank = 011    return start

1. Fact 1 first: if the totals do not cover the road, return −1.
2. Drive from the current candidate. When the tank goes negative at station i, Fact 2 rules out every station from start to i. Move the candidate to i + 1 with an empty tank.
3. Whatever candidate survives to the end is the answer. You do not need to drive round the wrap: the proof above shows it succeeds.

Dry run on gas = [4, 1, 3, 1, 5], cost = [2, 4, 2, 3, 2] (totals 14 and 13, so an answer exists):

Answer 4. Station 1 was never tried as a start: the failure at i = 1 ruled out stations 0 and 1 together.

Complexity: O(n) time — sum twice and one loop. O(1) space.

Approach 3: the lowest point, directly

The proof suggests a second way to write it: track the running total and remember where it was lowest.

1def start_station_low_point(gas: list[int], cost: list[int]) -> int:2    """Start right after the lowest point of the running fuel total."""3    running = lowest = start = 04    for i in range(len(gas)):5        running += gas[i] - cost[i]6        if running < lowest:           # a new lowest point: start after it7            lowest = running8            start = i + 19    return start if running >= 0 else -1

It is the same O(n) time and O(1) space, and it folds the total check into the same loop — running at the end is the total. On the example the running total goes 2, −1, 0, −2, 3; the lowest point is −2 after station 3, so the answer is 4 again. Both versions were tested against the brute force on 2,000 random inputs.

Edge cases

• One station, gas = [5], cost = [4]: total gain is +1, answer 0.
• Totals exactly equal: an answer still exists; the tank arrives back at the start with exactly 0.
• Every station alone is short, but the loop works, gas = [3, 1, 1], cost = [1, 2, 2]: station 0 banks +2, which covers the two −1 stations. Answer 0.
• Not enough fuel overall: caught before the loop.

Follow-ups

• Return every valid start when uniqueness is not promised? Every index where the running total hits its minimum (ties included) is a valid start; collect them in the low-point version.
• The tank has a capacity limit? The greedy breaks: extra fuel is lost, so the order of choices matters. Simulate from each candidate, or use a sliding window over the doubled array.
• Fewest refuelling stops on a straight road? A different greedy: pass stations, push their fuel into a max-heap, and pop the biggest only when you run dry — see Heaps.