134. Gas Station

There are n gas stations in a circle; station i has gas[i] and driving to station i+1 costs cost[i]. Starting with an empty tank, return the station index from which you can drive around once clockwise, or -1. The answer is unique if it exists.

If total gas < total cost, no start works. Otherwise, whenever the running tank goes negative at i, no start in [start, i] can work either, so restart at i + 1.

1function canCompleteCircuit(gas: number[], cost: number[]): number {
2  let total = 0, tank = 0, start = 0;
3  for (let i = 0; i < gas.length; i++) {
4    const d = gas[i] - cost[i];
5    total += d; tank += d;
6    if (tank < 0) { start = i + 1; tank = 0; }
7  }
8  return total < 0 ? -1 : start;
9}