Gas Station

Difficulty: Medium

There are several gas stations arranged in a circle. At station i, you can pick up gas[i] amount of fuel, and it costs cost[i] fuel to drive from station i to the next station. You start with an empty tank at whichever station you choose.

Determine the index of the station you should start at so that you can complete the entire circuit (visiting every station and returning to the start) without your tank ever going negative. If it's impossible from any starting station, return -1. You're guaranteed that if an answer exists, it's unique.

Examples

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

Starting at station 3: tank = 4-1=3, then +5-2=6, then +1-3=4, then +2-4=2, then +3-5=0. You never go negative and make it all the way around.

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

Total gas (9) is less than total cost (10), so no starting point can complete the circuit.

Constraints

n == gas.length == cost.length
1 <= n <= 10^5
0 <= gas[i], cost[i] <= 10^4

Approach

Trying every possible starting station and simulating the whole loop for each one works but is slow. There's a greedy shortcut: if the total gas available across the whole circuit is less than the total cost, it's impossible no matter where you start, so check that first.

Otherwise, a solution is guaranteed to exist, and you can find it in one pass. Walk around once from station 0, keeping a running tank total. Whenever the running total goes negative at some station, none of the stations you've passed through since your current candidate start could have worked either (starting a bit later only ever means a smaller-or-equal running total up to any point) - so the failure "resets" your candidate start to the very next station.

Solutions

Brute Force - Simulate From Every Start

Try starting at every station, and simulate a full trip around the circuit, giving up as soon as the tank goes negative.

function canCompleteCircuit(gas, cost) {
  const n = gas.length;
  for (let start = 0; start < n; start++) {
    let tank = 0;
    let steps = 0;
    for (; steps < n; steps++) {
      const i = (start + steps) % n;
      tank += gas[i] - cost[i];
      if (tank < 0) break;
    }
    if (steps === n) return start;
  }
  return -1;
}

Time: O(n^2) · Space: O(1)

Optimal - Greedy One Pass

Check feasibility using the total gas vs total cost, then find the start by resetting the candidate start every time the running tank dips negative.

function canCompleteCircuit(gas, cost) {
  let totalTank = 0;
  let currTank = 0;
  let start = 0;

  for (let i = 0; i < gas.length; i++) {
    const diff = gas[i] - cost[i];
    totalTank += diff;
    currTank += diff;
    if (currTank < 0) {
      start = i + 1;
      currTank = 0;
    }
  }

  return totalTank < 0 ? -1 : start;
}

Time: O(n) · Space: O(1)