Gas station: circular greedy in Python

Why this matters

Some problems go around in a loop. A bus runs a circular route. A delivery van returns to its depot. A race car does laps. In each case the question is whether the trip can finish, and where it should begin.

The gas station problem is the classic version. It needs a running total, and one new idea: a circle has no end, so the start point matters. A naive solution tries every start and checks the whole loop each time. That takes about n times n steps, where n is the number of stations. The greedy solution finds the answer in one pass. A greedy method makes the choice that looks best at each step, and it never goes back to change that choice.

By the end of this lesson you will be able to turn the fuel problem into a running balance, find the start in Python with one loop, prove why the start is safe, and test the function against a brute-force search. Brute force means trying every possibility. You will also see one claim that is often repeated and is not true: that the answer is always unique.

The problem in plain words

There are n gas stations on a circle, numbered from 0 to n - 1. Station n - 1 is next to station 0, so the trip wraps around.

You are given two lists of the same length:

• gas[i] is the number of litres you can fill at station i.
• cost[i] is the number of litres you burn to drive from station i to the next station.

A litre is a unit of fuel. The lists are called gas and cost in the Python code. The name cost is short for the fuel cost of that road, not money.

You start at one station with an empty tank. At each station you fill up with gas[i], then drive away and burn cost[i]. You may not drive if the tank would go below zero, because the car stops. The question is: which station can you start from so that you drive all the way around and arrive back at the start?

Take this example:

station:  0  1  2  3  4
gas:      1  2  3  4  5
cost:     3  4  5  1  2

From station 0 you fill 1 litre and need 3 to reach station 1. You cannot make it. From station 3 you fill 4 litres, drive for 1, and so on. Station 3 is the answer, as the rest of the lesson shows.

The idea: the net fuel at each station

Look at each station as a single number. At station i, you gain gas[i] and lose cost[i]. The net fuel at that station is:

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

A positive diff means the station gives you more fuel than the road takes. A negative diff means the road takes more than the station gives.

For the example:

station:  0   1   2   3   4
diff:    -2  -2  -2   3   3

The sum of all the differences is -2 - 2 - 2 + 3 + 3 = 0. Call this sum the total. The total tells you whether a full lap is possible at all. After one full lap you have visited every station once, so the fuel you have left equals the total. If the total is negative, you ran out somewhere, so no start works.

Walk the example by hand

Now the question becomes: where can the trip start so the tank never runs dry? Keep a running balance called tank. It is the fuel you have after the stations you have visited since your last start. Go through the stations in order and add each diff to tank.

Start with tank = 0 at station 0.

• Station 0: tank = 0 + (-2) = -2. The tank went below zero, so station 0 cannot be the start, and station 1 is the next candidate. Reset: start at station 1 and set tank = 0.
• Station 1: tank = 0 + (-2) = -2. Below zero again, so start at station 2 and reset tank = 0.
• Station 2: tank = 0 + (-2) = -2. Below zero, so start at station 3 and reset tank = 0.
• Station 3: tank = 0 + 3 = 3. No problem.
• Station 4: tank = 3 + 3 = 6. No problem.

The last start you set is station 3, and the total is 0, which is not negative. So the answer is station 3.

Check it by driving from station 3. Use the real numbers:

start at station 3, tank 0
fill 4 at station 3, drive 1  -> tank 3
fill 5 at station 4, drive 2  -> tank 6
fill 1 at station 0, drive 3  -> tank 4
fill 2 at station 1, drive 4  -> tank 2
fill 3 at station 2, drive 5  -> tank 0
arrived back at station 3 with 0 litres

The tank never went below zero, and you finished the lap. Now check the stations that the scan rejected. Starting at stations 0, 1 or 2 fails on the first road, since each of those stations is 2 litres short.

Why does the scan reset the tank to zero? The rule is this: if your tank went negative after station i, then no start between your old start and station i can work. Each of those starts reaches station i with even less fuel than the start you already tried, so you move the start to i + 1 and begin a fresh balance. This is the greedy choice. It jumps the start forward past a dead end, and it never goes back.

The Python code

The function takes two lists and returns a number. The type hints such as list[int] and -> int say what kind of values go in and out. Python does not check them while the program runs. They are notes for readers and for tools.

enumerate gives you each item's position together with the item. zip pairs items from two lists, so (fill, burn) is one pair taken from gas and cost at the same position. Here fill is gas[i] and burn is cost[i].

def can_complete_circuit(gas: list[int], cost: list[int]) -> int:
    total = 0
    tank = 0
    start = 0
    for i, (fill, burn) in enumerate(zip(gas, cost)):
        diff = fill - burn
        total += diff
        tank += diff
        if tank < 0:
            start = i + 1
            tank = 0
    if total < 0:
        return -1
    return start

The loop does one pass. It keeps two running numbers: total for the full lap, and tank for the current stretch. The function returns -1 when total is negative. Otherwise it returns the start that the scan has chosen.

The zip call stops at the shorter of the two lists. If gas and cost have different lengths, the extra items are ignored without an error. Check that the lists match before you call the function.

The returned start is always a valid index when the function does not return -1. The proof below explains why.

Here is the output for several inputs. Each line shows the input, the answer from the function, and every start that works, found by trying each station. The program that prints these lines is in the brute-force section below.

gas=[1, 2, 3, 4, 5] cost=[3, 4, 5, 1, 2] -> start=3 valid_starts=[3]
gas=[2, 3, 4] cost=[3, 4, 3] -> start=-1 valid_starts=[]
gas=[2, 1] cost=[1, 1] -> start=0 valid_starts=[0, 1]
gas=[1, 1] cost=[1, 1] -> start=0 valid_starts=[0, 1]
gas=[5, 1, 2, 3, 4] cost=[4, 4, 1, 5, 1] -> start=4 valid_starts=[4]
gas=[1, 2, 1, 3] cost=[2, 1, 2, 1] -> start=1 valid_starts=[1, 3]

The second line shows the total check. The total of [2, 3, 4] minus [3, 4, 3] is -1, so no start works and the answer is -1.

The third and fourth lines show something important. The answer 0 is correct, but station 1 also works. The next section explains why.

Why the start is always valid when the total is not negative

This proof has three parts. Read it slowly, with a concrete example at hand. Use the input gas = [5, 1, 2, 3, 4] and cost = [4, 4, 1, 5, 1]. The differences are 1, -3, 1, -2, 3. The total is 0.

First, run the scan and write down the running balance after each station, without resets. It is 1, -2, -1, -3, 0. The scan resets at station 1, where the balance is -2, and at station 3, where the tank since the last reset is -1 (the running balance is -3). So the final start is station 4.

Part 1: the last stretch never runs dry

Let s be the final start. After the last reset, the scan never dropped below zero. So if you start at s with an empty tank, you never run out on the stretch from s to the end of the list. Call the net fuel on that stretch R.

In the example, s = 4, the stretch is just station 4, and R = 3. The tank never went below 0.

Part 2: the earlier stations never fall below a fixed level

Now look at the part from station 0 to station s - 1. Call the running balance at station s - 1 Q. In the example, Q is the balance after station 3, which is -3.

Here is the key fact: every station in that part has a balance that is at least Q. Two things make this true.

• Each earlier stretch between two resets ended with a negative tank. So the net fuel of each stretch is negative. That makes the balance lower at each reset than at the reset before it. In the example, the balance at reset 1 is -2 and at reset 3 is -3, so it gets lower.
• Between two resets, the balance stays above the balance at the reset that ends the stretch. The scan did not reset during that stretch, so the tank never went negative inside it, and the balance at any station in the stretch is higher than the balance at the stretch's reset.

Together, these mean the lowest balance in the earlier part is the one at s - 1. In the example, the balances at stations 0 to 3 are 1, -2, -1, -3. The lowest is -3, which is Q.

Part 3: the wrap-around never goes below zero

Now start at s and drive around. When you reach the earlier stations, after you finish the last stretch, your tank holds R plus the balance at that station. From Part 2, that balance is at least Q. So the tank holds at least R + Q.

The sum R + Q is the total of the whole list, which is T. The total is not negative by assumption, so the tank never goes below zero.

For the example, the tank values during the wrap are 3 + 1 = 4, 3 + (-2) = 1, 3 + (-1) = 2, and 3 + (-3) = 0. The smallest is 0, which equals the total. Nothing went negative.

Why the start can never be n

Each reset happens where the balance is below zero, and each later reset happens at a lower balance. So every reset value is negative. A reset at the last station would set the start to n, and the balance there equals the total, so the total would be negative. In that case the function returns -1. So when the total is not negative, the start is a number from 0 to n - 1.

Why the answer is not unique

Some problem statements promise that the answer is unique. The arithmetic does not give that promise. Look at the third line of the output again: gas = [2, 1] and cost = [1, 1].

Check both starts by hand.

• Start at station 0. Fill 2, drive 1, tank 1. Arrive at station 1, fill 1, drive 1, tank 1. Back at station 0 with 1 litre. Works.
• Start at station 1. Fill 1, drive 1, tank 0. That is not negative, so you can drive. Arrive at station 0, fill 2, drive 1, tank 1. Arrive at station 1 with 1 litre. Works.

Both starts work. The total here is 1, which is positive, so the total test does not rule out station 1. The scan still returns station 0, because no balance went below zero, so it never reset.

A test that expects exactly one answer would fail on this input. The random test below found this too: among 200,000 random small inputs, 73,496 had more than one valid start. So when you write a solution, return any valid start, and do not depend on the answer being the only one.

Two more examples

An example with one reset

Take gas = [1, 2, 1, 3] and cost = [2, 1, 2, 1]. The differences are -1, 1, -1, 2, and the total is 1.

Without resets, the running balance is -1, 0, -1, 1. The scan resets at station 0, where the balance is -1, so the start becomes 1. After that reset the balance is 1, 0 and then 2, and it never goes below zero, so there are no more resets. The output is:

gas=[1, 2, 1, 3] cost=[2, 1, 2, 1] -> start=1 valid_starts=[1, 3]

Start 1 is the scan's answer. Start 3 also works, which is another example of more than one valid start.

An example where the total is negative

Take gas = [2, 3, 4] and cost = [3, 4, 3]. The differences are -1, -1, 1, and the total is -1.

The scan resets at station 0 and station 1, and returns start 2 if you ignore the total. The function must check the total first. With a total of -1, you burn one more litre than you collect over a full lap. Whatever start you choose, the tank must run out before the lap ends. So the answer is -1.

The output confirms this:

gas=[2, 3, 4] cost=[3, 4, 3] -> start=-1 valid_starts=[]

Checking the code with a brute-force search

The brute-force method tries every start and drives the full lap from each one. It takes about n times n steps, which is slow for big inputs but easy to trust. The function works_from drives one lap from one start, and valid_starts tries every start.

The % n is what makes the trip wrap around. Station (s + k) % n is the station you are at after k steps from s. Without it, the index runs past the end of the list, as the mistakes section shows.

The random check below uses the three functions from the block above. It generates 200,000 inputs with up to 8 stations each, with gas and cost values from 0 to 4. It uses a fixed seed, so every run gives the same numbers. For every input, the function must return -1 exactly when no start works, and otherwise return a start that works_from accepts:

import random
 
rng = random.Random(1)
checked = 0
multi = 0
for _ in range(200_000):
    n = rng.randint(1, 8)
    gas = [rng.randint(0, 4) for _ in range(n)]
    cost = [rng.randint(0, 4) for _ in range(n)]
    valid = valid_starts(gas, cost)
    answer = can_complete_circuit(gas, cost)
    if valid:
        assert answer in valid, (gas, cost, answer, valid)
    else:
        assert answer == -1, (gas, cost, answer)
    checked += 1
    if len(valid) > 1:
        multi += 1
 
print(f"random cases checked: {checked}")
print(f"cases with more than one valid start: {multi}")

The output is:

random cases checked: 200000
cases with more than one valid start: 73496

The count changes with the random seed, so a different seed gives a different number. The assertions passed for every case, so the function agreed with the brute-force check on all 200,000 inputs.

Common mistakes

Forgetting to reset the tank

After a reset, the tank must go back to zero. If it keeps its negative value, the next stretch starts with a debt, and the start moves to the wrong place. Here is a version that skips the reset:

def no_reset(gas: list[int], cost: list[int]) -> int:
    total = 0
    tank = 0
    start = 0
    for i, (fill, burn) in enumerate(zip(gas, cost)):
        diff = fill - burn
        total += diff
        tank += diff
        if tank < 0:
            start = i + 1
    if total < 0:
        return -1
    return start % len(gas)
 
 
print(no_reset([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]))

It prints 4 for gas = [1, 2, 3, 4, 5] and cost = [3, 4, 5, 1, 2]. The correct answer is 3. Starting at station 4 fails: you arrive at station 1 with 1 litre, fill 2 there, and still cannot cover the 4 litres the road costs.

Setting the start to the failing station instead of the next one

When the tank goes negative at station i, the next station to try is i + 1. A version that sets start = i tries the station that just failed:

def start_is_i(gas: list[int], cost: list[int]) -> int:
    total = 0
    tank = 0
    start = 0
    for i, (fill, burn) in enumerate(zip(gas, cost)):
        diff = fill - burn
        total += diff
        tank += diff
        if tank < 0:
            start = i
            tank = 0
    if total < 0:
        return -1
    return start
 
 
print(start_is_i([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]))

On the first example it prints 2, while the correct answer is 3:

2

Station 2 burns 5 litres and gives only 3, so it cannot be the start.

Returning the start without checking the total

The scan always produces some start, even when the total is negative. Without the check, the answer is wrong. On gas = [2, 3, 4] and cost = [3, 4, 3], this version prints 2, and the correct answer is -1:

def no_total_check(gas: list[int], cost: list[int]) -> int:
    tank = 0
    start = 0
    for i, (fill, burn) in enumerate(zip(gas, cost)):
        tank += fill - burn
        if tank < 0:
            start = i + 1
            tank = 0
    return start
 
 
print(no_total_check([2, 3, 4], [3, 4, 3]))

2

Reading past the end of the list

Without % n, the index for a wrap-around station runs past the end. Here is a small program with that bug, saved as wrap_bug.py:

def wrap_wrong(gas: list[int], cost: list[int], s: int) -> int:
    tank = 0
    for k in range(len(gas)):
        i = s + k
        tank += gas[i] - cost[i]
        if tank < 0:
            return -1
    return 0
 
 
print(wrap_wrong([1, 2, 3], [1, 1, 1], 1))

Starting at station 1 means i runs through 1, 2, 3. The index 3 does not exist in a list of length 3. Python stops with this error, where the folder part of the file path is left out:

Traceback (most recent call last):
  File "wrap_bug.py", line 11, in <module>
    print(wrap_wrong([1, 2, 3], [1, 1, 1], 1))
          ~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^
  File "wrap_bug.py", line 5, in wrap_wrong
    tank += gas[i] - cost[i]
            ~~~^^^
IndexError: list index out of range

The last line gives the error type, IndexError, and the message. The lines above it show where the error happened. The fix is i = (s + k) % len(gas).

Python has one more trap here, and it is quieter. A negative index does not fail. cost[-1] is the last item in the list, so a bug that makes i negative reads the wrong station without any error:

cost = [4, 5, 6]
print(cost[-1])

6

Assuming the answer is unique

A test that insists on one exact start breaks when another correct method returns a different valid start. For gas = [2, 1] and cost = [1, 1], either 0 or 1 is right. Check that the returned start passes works_from.

Practice

Exercise 1. Use the scan on gas = [1, 2, 1, 3] and cost = [2, 1, 2, 1]. Write the running balance after each station, then give the start the scan returns.

Show the answer

The differences are -1, 1, -1, 2. The balance after each station, with resets, is: station 0, tank -1, so reset and start at 1; station 1, tank 1; station 2, tank 0; station 3, tank 2. The scan returns start 1. Start 3 also works, as the output in the examples shows.

Exercise 2. For gas = [3, 1, 1] and cost = [1, 2, 2], find every start that works. Do not use the scan. Drive the lap by hand from each station.

Show the answer

Only station 0 works. The differences are 2, -1, -1. From station 0 the tank goes 2, then 1, then 0, and never drops below zero. From station 1 the first road costs 2 and the tank holds only 1, so the trip fails. From station 2 the first road costs 2 and the tank holds 1, so it also fails. The list of valid starts is [0].

Exercise 3. For gas = [1, 2] and cost = [2, 1], find the answer that the scan returns. Then explain why the answer is not -1, even though station 0 alone cannot make the trip.

Show the answer

The differences are -1, 1. The total is 0, which is not negative, so the function does not return -1. The scan resets at station 0, so the start is 1. Check it: fill 2 at station 1 and drive 1, leaving 1 litre. At station 0 fill 1, making 2 litres, and drive 2, leaving 0 when you reach station 1 again. The answer is 1.

Exercise 4. Explain in plain words why gas = [2, 3, 4] and cost = [3, 4, 3] has no valid start, using only the total.

Show the answer

Over one full lap you visit every station once, so the fuel you have at the end equals the total of all the differences. The total is -1, so you end the lap one litre short. A tank that ends negative must have dropped below zero at some point on the way, and the car would have stopped. So no start can finish the lap.

Exercise 5. Using the scan for gas = [2, 1] and cost = [1, 1], explain why the answer is 0 even though station 1 also works.

Show the answer

The differences are 1, 0. The tank after station 0 is 1, and after station 1 it is 1, so it never drops below zero. The scan never resets, so the start stays at 0. Station 1 also works: starting there, the tank is 0 after the first road, which is allowed, and then station 0 gives 2 more litres. The scan only keeps the start it has, and there can be other valid starts.

Summary

• Turn each station into a net fuel number, gas[i] - cost[i], and keep a running balance that resets when it goes below zero.
• If the total of all the net fuel numbers is negative, no start works, so return -1.
• The last start the scan sets is valid whenever the total is not negative. The proof has three parts, and each part uses the fact that every reset happens at a negative balance.
• More than one start can work. Return any valid one, and do not write tests that expect a single answer.
• Check the greedy function against a brute-force search that drives the full lap from every start.