Gas station: circular greedy

Why this matters

Some problems run in a circle. A bus route returns to its first stop. A race track has no finish line that is different from the start. A round-the-world plan visits the same cities in order. In each case you want to know whether one trip around the circle is possible, and if so, where to begin.

The naive way to answer this is to try every starting point and drive the whole circle from each one. That costs about n * n steps for n stations, which is slow when the circle has many stations. This lesson shows a method that finds a working start in one pass. It is greedy: it keeps a single running number, and when that number goes wrong, it makes one choice (restart after the failure) and never goes back.

You need for loops, std::vector, std::size_t and long long from earlier lessons. The jump game lesson earlier in this module uses a similar greedy idea on a line instead of a circle. You do not need that lesson to follow this one.

The problem in a picture

Imagine a circle of four gas stations numbered 0 to 3. Your car starts with an empty tank. At each station you can fill up with some fuel, and then you drive to the next station, which costs some fuel. The next station is the one after it on the circle, and station 3 leads back to station 0.

Two lists describe the trip.

• gas[i] is the fuel you can take on at station i.
• cost[i] is the fuel needed to drive from station i to the next station.

Take this example.

station:  0  1  2  3  4
gas:     [1, 2, 3, 4, 5]
cost:    [3, 4, 5, 1, 2]

At station 0 you get 1 unit of fuel and need 3 to reach station 1. That is a shortfall of 2. At station 3 you get 4 and need 1, which is a surplus of 3. The question is: which station can you start from, with an empty tank, so that you visit all five stations and return to the start without ever running out of fuel?

The task is to return that station's index, or -1 if no start works. An index is a position in a list, counted from zero.

Step one: the total decides whether an answer exists

Give each station a net change of fuel. The net change is what you gain at a station minus what you spend driving away from it:

change[i] = gas[i] - cost[i]

For the example, the changes are [-2, -2, -2, 3, 3].

Add all the changes together to get the total. If the total is negative, you spend more fuel than you collect on one full lap, and no start can succeed. Return -1 at once. If the total is zero or more, a working start always exists. Step two finds it.

For the example, the total is -2 - 2 - 2 + 3 + 3 = 0. It is zero, so an answer exists.

A second example shows the case that fails. Take gas = [2, 3, 4] and cost = [3, 4, 3]. The changes are [-1, -1, 1], and the total is -1. Every lap loses one unit, so the answer is -1.

Step two: a running balance and a restart rule

Now walk around the circle from one starting point, keeping a running number called tank. This is the fuel you have left as you arrive at each station, counting from the start you chose. You begin with tank = 0.

For each station i, add its change to tank. If tank ever becomes negative, you ran out of fuel somewhere on the way, so that start failed. The rule is:

• If tank goes below zero at station i, the start cannot be any station from the old start up to i. Set the new candidate start to i + 1, and reset tank to 0.

Here is the walk for the example. The candidate start begins at 0.

The candidate at the end is 3. The total is 0, which is not negative, so the answer is 3. You can check it by driving from station 3. The changes in order are +3, +3, then -2, -2, -2. The tank goes 3, 6, 4, 2, 0. It never drops below zero, and it ends exactly at zero when you return to station 3.

Why reset to i + 1 and not to i? The tank was zero or more before station i, and it went below zero after adding station i's change. So that change must be negative. Starting at i with an empty tank would run short at once, so the next candidate is i + 1. In the table above, station 2 has a change of -2, so the candidate moves on to station 3.

The code

The function reads the list once. The running time grows in a straight line with the number of stations.

#include <cstddef>
#include <vector>
 
int canCompleteCircuit(const std::vector<int>& gas, const std::vector<int>& cost) {
    long long total = 0;
    long long tank = 0;
    std::size_t start = 0;
    for (std::size_t i = 0; i < gas.size(); ++i) {
        const long long change = static_cast<long long>(gas[i]) - cost[i];
        total += change;
        tank += change;
        if (tank < 0) {
            start = i + 1;
            tank = 0;
        }
    }
    return total < 0 ? -1 : static_cast<int>(start);
}

The variable total and tank are long long. The fuel amounts in real problems can be large, and adding many of them can overflow a plain int. The static_cast<long long> before subtracting makes sure the subtraction is done in the wider type.

The function returns static_cast<int>(start). In the case where the total is zero or more, start is always less than gas.size(). The reason is explained in the next section, so you can rely on it when you read the proof.

Why the answer is correct

The method makes two claims. Both need a proof, because the greedy steps look like guesses until you see why they hold.

Claim one: a failed start rules out the stations before the failure

Suppose you start at station s and the tank first goes negative at station i. Then no start from s through i can work.

Take any station t between s + 1 and i. Starting from s, you reached t without running out, so the fuel from s up to t - 1 never went negative. That means the fuel collected from s up to t - 1 is zero or more. You also know that the fuel from s up to i is negative, because that is where it failed. If you subtract the first part from the second, you get that the fuel from t up to i is negative. So starting at t runs out before reaching i.

This is why the code can move the candidate straight to i + 1. It does not need to test the stations in between.

Claim two: when the total is zero or more, the final candidate works

Let s be the final candidate. Its walk from s to the last station never failed, because the candidate would have moved again if it had. So the part of the circle from s to the end has no negative running total.

The stations before s came in failed stretches. Each failed stretch ended with a negative running total. Claim one also shows that every tail of a failed stretch adds up to zero or less. A tail is the part of a stretch that starts partway through. Adding up the tails that come before s gives a total of zero or less.

Now look at the whole circle. Its total is T, which is zero or more. The stretch from s to the end adds up to T minus the stretch before s. Since the stretch before s is zero or less, the stretch from s to the end is at least T, so it is zero or more.

The walk then wraps around to the stations before s. After station k, where k is before s, the fuel from s is the stretch from s to the end, plus the changes from station 0 to k. That sum equals T minus the changes from station k + 1 to s - 1. Those changes are a tail of the failed stretches, so they add up to zero or less. So the fuel is at least T, which is zero or more, and the walk never goes negative. So s works.

The proof also shows why start is never gas.size() when the total is zero or more. If the last station caused a reset, every stretch in the walk ended negative, so the total would be negative. That contradicts the test.

Uniqueness: what is true and what is not

It is tempting to think that the working start is always the only one. It is not. Here is the case with two.

Take gas = [1, 0, 1] and cost = [0, 1, 0]. The changes are [1, -1, 1], and the total is 1.

Start at station 0. The tank goes 1, then 0, then 1. It never drops below zero, so the trip works.

Start at station 2. The tank goes 1 at station 2, then 2 at station 0, then 1 at station 1, and it arrives back at station 2 with 1 left. It also works.

The greedy method returns 0, which is one of the two. The method is correct because it returns a working start. Other working starts can exist as well. Exercise 4 below gives a function that checks one start, so you can list all of them yourself.

Worked examples

Example one: the zero total

Take gas = [2, 2, 2] and cost = [2, 2, 2]. Every change is 0, and the total is 0. No station ever makes the tank negative, so the candidate stays at 0. Every station works as a start, and the function returns 0.

Example two: a single restart

Take gas = [1, 2, 3] and cost = [2, 2, 2]. The changes are [-1, 0, 1].

Station 0 gives tank = -1, so the candidate becomes 1 and the tank resets. Station 1 gives 0, which is not negative, so the candidate stays at 1. Station 2 gives 1. The total is 0, so the function returns 1. Starting at station 1 works: the changes in order are 0, 1, then -1, and the tank never goes below zero.

Example three: a full program with output

The program below runs the function on the examples from this lesson and prints the answers.

#include <cstddef>
#include <iostream>
#include <vector>
 
int canCompleteCircuit(const std::vector<int>& gas, const std::vector<int>& cost) {
    long long total = 0;
    long long tank = 0;
    std::size_t start = 0;
    for (std::size_t i = 0; i < gas.size(); ++i) {
        const long long change = static_cast<long long>(gas[i]) - cost[i];
        total += change;
        tank += change;
        if (tank < 0) {
            start = i + 1;
            tank = 0;
        }
    }
    return total < 0 ? -1 : static_cast<int>(start);
}
 
int main() {
    std::cout << canCompleteCircuit({1, 2, 3, 4, 5}, {3, 4, 5, 1, 2}) << '\n';
    std::cout << canCompleteCircuit({2, 3, 4}, {3, 4, 3}) << '\n';
    std::cout << canCompleteCircuit({1, 0, 1}, {0, 1, 0}) << '\n';
    std::cout << canCompleteCircuit({5, 1, 2, 3, 4}, {4, 4, 1, 5, 1}) << '\n';
    std::cout << canCompleteCircuit({2, 2, 2}, {2, 2, 2}) << '\n';
    std::cout << canCompleteCircuit({1, 2, 3}, {2, 2, 2}) << '\n';
}

Build and run it.

g++ -std=c++20 -Wall -Wextra -o gas gas.cpp
./gas

The output is as follows.

3
-1
0
4
0
1

The first output is the example from the walkthrough. The second is the case with a negative total. The third is the case with two working starts, where the method returns the first one it finds. The fourth is a longer circle where only station 4 works. The last two match the worked examples above.

Common mistakes

Forgetting the total check

Without the total check, the function can return a station even when no trip is possible. Here is the version with the check removed.

int noTotalCheck(const std::vector<int>& gas, const std::vector<int>& cost) {
    long long tank = 0;
    std::size_t start = 0;
    for (std::size_t i = 0; i < gas.size(); ++i) {
        tank += static_cast<long long>(gas[i]) - cost[i];
        if (tank < 0) {
            start = i + 1;
            tank = 0;
        }
    }
    return static_cast<int>(start);
}

For gas = {2, 3, 4} and cost = {3, 4, 3}, this version prints 2. The correct answer is -1, because the total is -1. Starting at station 2 fails at station 1: the tank is 1 after station 2, then 0 after station 0, then -1 after station 1.

Not resetting the tank

If the code moves the start but keeps the old tank, the fuel from the failed stretch carries into the new one. Here is the version without the reset.

int noTankReset(const std::vector<int>& gas, const std::vector<int>& cost) {
    long long tank = 0;
    std::size_t start = 0;
    for (std::size_t i = 0; i < gas.size(); ++i) {
        tank += static_cast<long long>(gas[i]) - cost[i];
        if (tank < 0) {
            start = i + 1;
        }
    }
    return static_cast<int>(start);
}

For gas = {1, 2, 3, 4, 5} and cost = {3, 4, 5, 1, 2}, this version prints 4. The correct answer is 3. The tank keeps the early losses, so it is still negative at station 3, and the start moves to 4, which does not work.

Setting the start to the failing station

Some people write start = i instead of start = i + 1. The failing station has a negative change, so it cannot be a start either. Here is that version.

int startAtFailure(const std::vector<int>& gas, const std::vector<int>& cost) {
    long long tank = 0;
    std::size_t start = 0;
    for (std::size_t i = 0; i < gas.size(); ++i) {
        tank += static_cast<long long>(gas[i]) - cost[i];
        if (tank < 0) {
            start = i;
            tank = 0;
        }
    }
    return static_cast<int>(start);
}

For the same example, this version prints 2. The correct answer is 3. Station 2 fails on its own, so the start has to move past it.

A compiler warning about signed and unsigned numbers

Comparing an int loop counter with gas.size() gives a warning. Here is a small program with that mistake, saved as sign.cpp.

#include <iostream>
#include <vector>
 
int main() {
    std::vector<int> gas{1, 2, 3};
    for (int i = 0; i < gas.size(); ++i) {
        std::cout << gas[i] << '\n';
    }
}

Building it with g++ -std=c++20 -Wall -o sign sign.cpp prints this warning.

sign.cpp: In function ‘int main()’:
sign.cpp:6:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
    6 |     for (int i = 0; i < gas.size(); ++i) {
      |                     ~~^~~~~~~~~~~~

Use std::size_t for the loop counter, as the functions in this lesson do.

Practice

Exercise 1. For gas = {1, 2, 3} and cost = {2, 2, 2}, find the answer and check it by driving the circle from that start.

Show the answer

The changes are -1, 0 and +1, and the total is 0. The running tank is -1 at station 0, which resets the candidate to 1. The answer is 1. Starting at station 1, the tank goes 0, +1, 0, and it never drops below zero.

Exercise 2. Use the function to decide whether gas = {1, 1} and cost = {2, 1} can complete the circle, and explain the answer using the total.

Show the answer

The changes are -1 and 0. The total is -1, which is negative. The function returns -1. No start works, because each lap loses one unit of fuel.

Exercise 3. Take gas = {1, 0, 1} and cost = {0, 1, 0}. List every station that works as a start, and explain why the greedy function can return only one of them.

Show the answer

Stations 0 and 2 both work. Starting at 0, the tank goes 1, 0, 1. Starting at 2, the tank goes 1, 2, 1. The greedy function returns 0, because it reaches the end of the loop without a reset and keeps the candidate it had. The function is still correct, because it returns a working start, but the answer is not unique.

Exercise 4. Write a function bool worksFrom(const std::vector<int>& gas, const std::vector<int>& cost, std::size_t s) that returns true when starting at station s completes the circle. Use it to check the answer from the greedy function.

Show the answer

#include <cstddef>
#include <vector>
 
bool worksFrom(const std::vector<int>& gas, const std::vector<int>& cost, std::size_t s) {
    const std::size_t n = gas.size();
    long long tank = 0;
    for (std::size_t k = 0; k < n; ++k) {
        const std::size_t i = (s + k) % n;
        tank += static_cast<long long>(gas[i]) - cost[i];
        if (tank < 0) {
            return false;
        }
    }
    return true;
}

The % n wraps the index back to station 0 after the last station. For the example gas = {1, 2, 3, 4, 5} and cost = {3, 4, 5, 1, 2}, worksFrom returns true only for s = 3, which matches the greedy answer. This function costs about n * n steps across all starts, so it is useful for checking, not for the final answer.

Exercise 5. The greedy function reads the list once. Explain in plain words why it does not need to try every start to be sure the answer is right.

Show the answer

Claim one in the proof says that a failed start rules out every station between the start and the failure. So the function can skip all of those stations at once by moving the candidate to the station after the failure. Claim two says that once the walk reaches the end without a failure, the candidate works, because the fuel gained from the start to the end covers the stretch that came before it. The function never needs a second pass, because each station is visited once and either moves the candidate or keeps it.

Summary

• Each station has a net change of fuel, gas[i] - cost[i]. The running total of those changes decides whether any start can work.
• If the total is negative, return -1. Otherwise, walk the circle with a running tank and restart after each failure at the station after the failure.
• The restart rule is safe because every station between a failed start and its failure also fails.
• When the total is zero or more, the final candidate works. The answer is not always the only working start.
• The two mistakes to avoid are skipping the total check and forgetting to reset the tank.