Gas station circuit
Medium TimeO(n) SpaceO(1)
Petrol stations sit in a circle. Station i gives gas[i] fuel, and driving from it to the next burns cost[i]. The tank starts empty and may never go negative between stations. Return the index of a station the whole loop can be completed from, or -1 when none works. The two arrays are the same length, and at most one starting station is ever valid.
Examples
Example 1
- Input
- gas = [1, 2, 3, 4, 5]cost = [3, 4, 5, 1, 2]
- Output
- From station 3:
3+3, then+3,-2,-2,+2— the tank never dips below zero.
Example 2
- Input
- gas = [2, 3, 4]cost = [3, 4, 3]
- Output
- The stations give 9 in total and the driving costs 10, so no lap is possible from anywhere.
-1
The Code
function canCompleteCircuit(gas, cost) {
let total = 0;
let tank = 0;
let start = 0;
for (let i = 0; i < gas.length; i++) {
const gain = gas[i] - cost[i];
total += gain;
tank += gain;
if (tank < 0) {
start = i + 1;
tank = 0;
}
}
return total >= 0 ? start : -1;
}
canCompleteCircuit([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]);Done