Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | 1x 1x 1x 1x 1x 1x 1x 1x 1x 2x 2x 2x 2x 2x 2x 2x 2x 7x 19x 19x 2x 2x 2x 17x 17x 17x 17x 19x 5x 5x 5x 19x 12x 12x 19x 7x 2x 2x 2x 1x 1x | // There are N gas stations along a circular route.
// Each has A[i] amount of gas.
// To travel from station i - i+1, there is B|i] cost.
// Find the earliest station from where you can travel around the entire circuit.
// Return -1 if not possible.
// • Constraints:
// • 1 <= N <= 16e
const gasStations = (gas: number[], cost: number[]): number => {
let result = -1;
let start = 0;
const doubleGas = gas.concat(gas);
const doubleCost = cost.concat(cost);
let currentGas = 0;
while (start < doubleGas.length && result === -1) {
for (let x = start; x < doubleCost.length; x++) {
// base case if this is a circle set result and end
if (x - start === gas.length) {
result = start;
break;
}
const newGas = doubleGas[x];
const newCost = doubleCost[x];
if (currentGas + (newGas - newCost) < 0) {
currentGas = 0;
start = x + 1;
break;
} else {
currentGas += newGas - newCost;
}
}
}
return result;
};
export default gasStations;
|