LeetCode 134 · Greedy

Gas Station, explained with a picture

A road trip around a ring of petrol stations.

MediumGreedy
▶ Watch it step by step

The problem

Gas stations sit on a circular road. At station i you can fill up gas[i], and driving to the next station costs cost[i]. Starting with an empty tank, from which station can you drive the whole loop? Return −1 if none.

Input:  gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]
Output: 3

Picture it

Picture a road trip around a ring of petrol stations. If the total fuel is less than the total cost, no start works. Otherwise drive from station 0 keeping a tank balance. If the tank ever goes negative, none of the stations from the current start up to here could be a valid start, so we restart the trip at the next station with an empty tank.

How to recognise it

  • Stations sit on a circle, and you must pick a starting point such that a running balance never goes below zero for a whole lap.
  • Each station contributes a net amount, gas[i] - cost[i], so the problem is about prefix sums of those amounts.
  • Up to 10^5 stations: trying each start with a full lap is O(n²), about 10^10 steps.
  • When one failure at position i rules out many starts at once, a greedy single pass is possible.

Start with brute force

Try every station as the start and simulate a lap, stopping as soon as the tank goes negative.

def circuit_brute(gas, cost):
    n = len(gas)
    for s in range(n):
        tank = 0; ok = True
        for k in range(n):
            i = (s + k) % n
            tank += gas[i] - cost[i]
            if tank < 0:
                ok = False; break
        if ok:
            return s
    return -1

Each start can need up to n steps, so time is O(n²): about 10^10 for n = 10^5, too slow. Space is O(1).

From brute force to the idea

  1. Total check first. If the total gas is less than the total cost, no start works, so return −1. If it is at least the total cost, some start does (this is the part that needs a short argument, given below).
  2. Run one lap from station 0, keeping a tank of net gas. If the tank falls below 0 at station i, you could not get past i from the current start.
  3. Rule out every start in between. The run from start had a tank of at least 0 at every station before i. A start at a later station k would arrive at each station up to i with a tank no bigger than that (it lacks the leftover from before k). So none of them can get past i either.
  4. Restart after the failure. Set start = i + 1 and tank = 0.
  5. Why the last start works. The total is non-negative, and all earlier failures were "debts" before start. The stretch from start to the end has a non-negative balance in every prefix (a negative prefix would have moved start again), and what is left is enough to cover the debts at the beginning of the circle.

This is the key idea: when the tank goes negative at i, no start up to i can work, so jump to i + 1; the total check guarantees the final candidate completes the lap.

The key idea

One pass: reset the start to i + 1 whenever the running tank drops below 0. O(n).

Python solution

def can_complete_circuit(gas, cost):
    if sum(gas) < sum(cost):
        return -1                       # not enough fuel in total
    tank, start = 0, 0
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0:                     # ran dry: no start up to i works
            start, tank = i + 1, 0
    return start

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(n²): up to n steps from each of n startsO(1): a tank value
Greedy (shown code)O(n): sum twice plus one loop, each linearO(1): tank and start

Edge cases

  • One station ([5], cost [4]): returns 0; with [1] and [1] it also returns 0 since the tank stays at 0.
  • Not enough total ([2, 3, 4] with cost [3, 4, 3]): returns -1.
  • Standard example ([1, 2, 3, 4, 5] with cost [3, 4, 5, 1, 2]): returns 3.
  • Ties ([3, 3] with cost [3, 3]): returns 0; both stations work here, and the problem guarantees the answer is unique, so this input does not occur.
  • Zero tank is fine: the code only restarts when the tank is strictly below 0, so arriving with exactly 0 is allowed.
  • Large values: Python integers do not overflow; in other languages sums of 10^5 values up to 10^4 stay within 32-bit range (10^9).

Common mistakes

  • Skipping the sum(gas) < sum(cost) check: for [2, 3, 4] with cost [3, 4, 3] the loop ends with start = 2 and returns 2 instead of −1.
  • Restarting at i instead of i + 1, which retries the very station that caused the failure.
  • Not resetting tank to 0 when restarting.
  • Simulating a full lap from the final start to verify it. The total check makes that unnecessary.
Your turn: how much fuel to begin?

You must start at station 0, but the tank may begin with some fuel. Find the smallest starting fuel that lets you drive the whole lap, or -1 if the total gas is less than the total cost. For gas [1, 2, 3, 4, 5] and cost [3, 4, 5, 1, 2] the answer is 6. Describe your approach, then write it if you like.

Compare with our answer

The tank after each station is the starting fuel plus the running total of gas - cost. It must never go below 0, so the starting fuel is the negative of the lowest running total (or 0 if that is never negative).

def min_start_fuel(gas, cost):
    if sum(gas) < sum(cost):
        return -1
    tank = worst = 0
    for g, c in zip(gas, cost):
        tank += g - c
        worst = min(worst, tank)
    return -worst

min_start_fuel([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]) is 6 and min_start_fuel([2, 3, 4], [3, 4, 3]) is -1. Time O(n), space O(1).

A strong answer mentions: prefix sums of net gas, the lowest prefix sum being the biggest deficit, starting worst at 0 so the answer is never negative, and the total check for the -1 case.

Check what stuck

1. A circular delivery route has n depots with net fuel gains and losses (some negative). You must find a depot to start from, with an empty tank, so the tank never goes negative on one lap. n is up to 100,000. Which approach fits best?

2. The code restarts start after every failure. Why is it still O(n) and not O(n²)?

3. A learner deletes the if sum(gas) < sum(cost): return -1 line. For which input does the function now return a wrong answer?

Score 60% or more and the lesson is marked complete.