Gas Station

Given gas and cost to travel to next station, find the station that can form circle and reach to staring station again.

Gas Station

Problem Statement

There are n gas stations arranged along a circular route. The amount of gas available at station i is gas[i].

You have a car with an unlimited gas tank. It costs cost[i] gas to travel from station i to the next station, i + 1. You start the journey with an empty tank, at some station of your choosing.

Find the starting station index where you can travel around the entire circuit, collecting gas[i] and spending cost[i] along the way, and make it all the way back to your starting point.

If this is not possible, return -1.

If a valid starting index does exist, it is guaranteed to be unique.

Examples

Example 1

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

Output: 3

Explanation:

• Start at station 3, and fill up with 4 units of gas. Tank = 0 + 4 = 4.
• Travel to station 4. Tank = 4 - 1 + 5 = 8.
• Travel to station 0. Tank = 8 - 2 + 1 = 7.
• Travel to station 1. Tank = 7 - 3 + 2 = 6.
• Travel to station 2. Tank = 6 - 4 + 3 = 5.
• Travel back to station 3. The cost is 5. The gas is just enough to make it back.

So the starting index 3 is returned.

Example 2

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

Output: -1

Explanation:

• Starting at station 0 or station 1 doesn't work, since there isn't enough gas to reach the next station.
• Starting at station 2, filling up with 4 units: Tank = 0 + 4 = 4.
• Travel to station 0. Tank = 4 - 3 + 2 = 3.
• Travel to station 1. Tank = 3 - 3 + 3 = 3.
• Traveling back to station 2 needs 4 units of gas, but only 3 are available.

So it's not possible to complete the circuit from any starting point.

Constraints

• n == gas.length == cost.length
• 1 ≤ n ≤ 10⁵
• 0 ≤ gas[i], cost[i] ≤ 10⁴
• The input is guaranteed to have a unique answer.

Solution

Step 1: Check If It's Possible at All

First, we check the total gas available across all stations, versus the total cost to travel the whole route.

• If the total cost is more than the total gas, it's simply impossible to complete the loop, no matter where we start. So we return -1 right away.

Step 2: Find the Starting Point

If it is possible, we look for the correct starting index using one pass through the array.

• We keep a running total, currentGas. At each station, we update it like this:

  currentGas = currentGas + (gas[i] - cost[i])
  

  This represents: the gas we already had, plus what we collect at this station, minus what it costs to leave it.

• If currentGas ever drops below zero, it means we've run out of gas at some point during the journey. This tells us something important: none of the stations we've visited so far (including our current starting guess) can be a valid starting point. So we:

  • Reset currentGas back to 0.
  • Move our starting guess to the next station (i + 1), and try again from there.

• By the time we reach the end of the array, whatever starting index we landed on is the correct answer — since the problem guarantees that a valid starting point exists and is unique (as long as total gas covers total cost).

The Important Question: What If the Wrapped-Around Stations Are Negative?

Suppose our final startingIndex is 3.

We successfully travel 3 → 4 → 5 and finish with currentGas = +5.

Now we still need to travel through 0 → 1 → 2 → 3 to complete the loop. What if those remaining stations have negative net values, and take away more than the 5 we have?

This is the key thing to understand.

We already checked that totalGas ≥ totalCost, which means:

sum(gas[i] - cost[i]) ≥ 0

In other words, the total net gas for the entire circle is never negative.

For example, suppose:

• Part 1 (3 → 4 → 5): gain = +10
• Part 2 (0 → 1 → 2 → 3, the wrapped-around part): gain = -7

The complete circle totals +10 - 7 = +3. So we finish with 3 gas remaining. The negative values in the wrapped-around part are allowed — they just can't be large enough to push us into the negatives overall, because the total gain of the whole circle is guaranteed to be non-negative.

If the wrapped-around part had required more than what we accumulated — for example:

• Part 1 = +10
• Part 2 = -12
• Total = -2

Then totalGas < totalCost would have been true from the start, and we would have already returned -1 before even searching for a starting point. So by the time we're checking a candidate starting point, we already know the full loop is possible — we just need to find where to start it.

Why Can't There Be a Better Starting Point Further Forward?

The reasoning here isn't that our current answer holds "the most positive value possible." Instead, it's because whenever a candidate fails, we eliminate the entire failed section — not just the one station that caused the failure.

For example, suppose we're testing startingIndex = 2, and we eventually run out of gas at station 5. This tells us something stronger than just "station 2 doesn't work" — it tells us that no station between 2 and 5 could have worked as a starting point either. That's because starting anywhere in that range would still run into the same shortfall by the time it reaches station 5.

So we don't just move to station 3 and try again — we jump straight to startingIndex = 6, skipping the entire failed range.

If station 6 also eventually fails, we eliminate its failed section too, and move forward again. This process looks like:

1. A candidate starting point fails.
2. Everything from that candidate through the failure point gets eliminated at once.
3. We try the very next station after the failure point.
4. If that fails too, we eliminate its failed section as well.
5. We keep going until we reach a candidate that survives all the way through.

Since we already know that totalGas ≥ totalCost, we know a valid starting point must exist somewhere. So this process is guaranteed to eventually land on it — and that final startingIndex is our answer.

Code

let gasStationJourney = function(gas, cost) {
    let sumCost = cost.reduce((partialSum, a) => partialSum + a, 0);
    let sumGas = gas.reduce((partialSum, a) => partialSum + a, 0);

    if (sumCost > sumGas) {
        return -1;
    }

    let currentGas = 0;
    let startingIndex = 0;

    for (let i = 0; i < gas.length; i++) {
        currentGas = currentGas + (gas[i] - cost[i]);
        if (currentGas < 0) {
            currentGas = 0;
            startingIndex = i + 1;
        }
    }
    return startingIndex;
};