Gas Stations

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

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.

Constraints

• gas.length == cost.length
• 1 ≤ gas.length, cost.length ≤ 10³
• 0 ≤ gas[i], cost[i] ≤ 10³

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).

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;
};