Gas Station

The problem

Gas stations stand in a circle, numbered from 0. At station i you take on gas[i] units of fuel, and driving from station i to the next one burns cost[i] units. After the last station comes station 0 again. You choose one station and start there with an empty tank. Return the number of the station from which you can drive the whole circle, back to where you started, without the tank ever dropping below zero. Return -1 if no station works. When one works, it is the only one.

What to write

function solve(gas: number[], cost: number[]): number

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

Output
3

Input
gas = [2,3,4]
cost = [3,4,3]

Output
-1

Constraints

When a solution exists it is unique.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   A working start, when there is one, is unique, so you are looking for a single station and never have to choose between two. There may also be none. A full circle takes on every station's gas and burns every cost once, whichever station you start from. What does that say about the totals?

2. Hint 2: Ask a smaller question

   Take gas 2, 1, 1, 5 and cost 1, 2, 3, 1. Starting at station 0, the tank drops below zero on the drive out of station 2. Before you try stations 1 and 2 as starts, compare: how much fuel did the first attempt bring to each of them, and how much does a fresh start bring?

3. Hint 3: Name the pattern

   An attempt that runs dry rules out its start and every station it passed: it reached each of them with a tank that was not negative, and a fresh start there has less or the same. So the next candidate is the station after the failure. Ruling them all out at once, for good, is a greedy choice. Read the lesson on greedy choice.

4. Hint 4: State the invariant

   No station before the candidate can be the answer. The tank holds the fuel gathered since the candidate, and it has not been below zero on the way. The total holds gas minus cost for every station visited so far, wherever you start.

5. Hint 5: Sketch the pseudocode

   total = 0, tank = 0, start = 0. For each station i: gain = gas[i] - cost[i]. Add gain to total and to tank. If tank is below 0: start = i + 1 and tank = 0. After the loop, return -1 if total is below 0, otherwise start.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

If a candidate route runs out of fuel, none of its intervening stations can be a valid start. Restart after the failure, then check the overall balance.

The slow way

Try every station as the start. Drive the circle from it, adding each station's gas and taking away each cost, and give up on that start when the tank drops below zero. Return the first start that gets all the way round, or -1 if none does. It is correct, but each of the n starts can pass up to n stations: up to n × n steps.

The insight

When an attempt runs dry, every station it passed is ruled out together with its start. The attempt reached each of them with fuel in the tank, or none, and still failed, so starting there with none cannot go better. So one pass settles every start. Whether the start that is left gets all the way round is decided by the total of gas minus cost.

Step by step

1. Start with station 0 as the candidate, an empty tank and a total of 0. The candidate is the start being tried, and the tank holds the fuel gathered since the candidate. The total adds up gas minus cost for every station, whatever the start, and decides at the end whether any start works.
2. Visit every station once, in order. One visit per station is enough, because a failed attempt is never repeated from the stations it passed. The drive past the end of the list, back to the candidate, is settled by the total.
3. Work out this station's gain: its gas minus the cost to drive on. Only the difference matters to the tank. A station that gives 4 and costs 1 to leave adds 3, and one that gives 1 and costs 3 takes 2 away.
4. Add the gain to the total for the whole circle and to the tank. The tank answers a question about this candidate: has the drive from the candidate stayed at zero or above? The total answers a question about the circle: is there enough gas for all the costs?
5. Tank below zero: make the next station the candidate, tank empty. The attempt has run dry, and no station it passed can do better, because each was reached with a tank at zero or above. This station cannot either: its own gain is negative. A new start has no fuel.
6. Return -1 if the whole circle loses fuel, otherwise the candidate. A total below zero means the costs exceed the gas, so every start runs dry somewhere. Otherwise the candidate works: what is left in the tank at the end of the list covers the losses of the earlier stations.

The same numbered steps are the comments in each solution.

function solve(gas, cost) {
  // 1. Start with station 0 as the candidate, an empty tank and a total of 0
  let total = 0,
    tank = 0,
    start = 0;
  // 2. Visit every station once, in order
  for (let i = 0; i < gas.length; i++) {
    // 3. Work out this station's gain: its gas minus the cost to drive on
    const delta = gas[i] - cost[i];
    // 4. Add the gain to the total for the whole circle and to the tank
    total += delta;
    tank += delta;
    // 5. Tank below zero: make the next station the candidate, tank empty
    if (tank < 0) {
      start = i + 1;
      tank = 0;
    }
  }
  // 6. Return -1 if the whole circle loses fuel, otherwise the candidate
  return total < 0 ? -1 : start;
}

function solve(gas: number[], cost: number[]): number {
  // 1. Start with station 0 as the candidate, an empty tank and a total of 0
  let total = 0,
    tank = 0,
    start = 0;
  // 2. Visit every station once, in order
  for (let i = 0; i < gas.length; i++) {
    // 3. Work out this station's gain: its gas minus the cost to drive on
    const delta = gas[i] - cost[i];
    // 4. Add the gain to the total for the whole circle and to the tank
    total += delta;
    tank += delta;
    // 5. Tank below zero: make the next station the candidate, tank empty
    if (tank < 0) {
      start = i + 1;
      tank = 0;
    }
  }
  // 6. Return -1 if the whole circle loses fuel, otherwise the candidate
  return total < 0 ? -1 : start;
}

def solve(gas, cost):
    # 1. Start with station 0 as the candidate, an empty tank and a total of 0
    total = tank = start = 0
    # 2. Visit every station once, in order
    for i, (fuel, spend) in enumerate(zip(gas, cost)):
        # 3. Work out this station's gain: its gas minus the cost to drive on
        delta = fuel - spend
        # 4. Add the gain to the total for the whole circle and to the tank
        total += delta
        tank += delta
        # 5. Tank below zero: make the next station the candidate, tank empty
        if tank < 0:
            start = i + 1
            tank = 0
    # 6. Return -1 if the whole circle loses fuel, otherwise the candidate
    return -1 if total < 0 else start

Example 1, traced

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

Output
3

Why it works

A failed attempt reached every station it passed with a tank at zero or above, and still ran dry. A fresh start there has an empty tank, which is no better, so skipping them all for good, the greedy choice, loses nothing. If the circle's total is not below zero, the last candidate reached the end of the list, and what its tank holds covers every earlier loss.

Time and space

Time O(n), extra space O(1). The loop makes one pass over the n stations, with one subtraction, two additions and one comparison at each, so the time is O(n). Three numbers are stored, the total, the tank and the candidate, whatever the number of stations: O(1) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Do not return the candidate without checking the total. In example 2 the candidate left after the loop is station 2, but the circle burns 10 and gives 9, so the answer is -1.
• Empty the tank when the candidate moves. A new start has no fuel, and no debt either. If the negative tank is carried along, example 1 returns 4 instead of 3.
• The station where the tank drops below zero is ruled out too, so the next candidate is the station after it. Keeping that station as the candidate makes example 1 return 2 instead of 3.

Pattern

Greedy choice. Builds on Maximum Subarray.

Keep going