A one-way loop road has n fuel stations, numbered 0 to n - 1 in the direction of travel; after station n - 1 the road comes back to station 0. Stopping at station i lets you take on gas[i] units of fuel, and driving from station i to the next one burns cost[i] units. Your tank has no upper limit.
You start with an empty tank at a station of your choice and drive once all the way round, back to where you started. The tank may touch 0 on arrival at a station, but it can never run out between two stations.
Return the index of the station you can start from to finish the lap, or -1 if no start works. Whenever a lap is possible, exactly one starting station makes it.
From station 3 the tank reads 6 - 1 = 5 on reaching station 4, then 5 + 1 - 3 = 3 at station 0, 4 at station 1, 1 at station 2, and exactly 0 back at station 3. Every other start runs dry on the way.
The stations hold 11 units of fuel between them, but one lap burns 12, so no starting point can make it.
Station 0 has the most fuel, yet starting there leaves 4 units for a leg that costs 6. Starting at station 2 instead reaches station 1 with 6 units in the tank, just enough for that leg.
Constraints
n == gas.length == cost.length1 <= n <= 10⁵0 <= gas[i], cost[i] <= 10⁴If the stations hold less fuel in total than the whole lap burns, no start can work and the answer is -1. Otherwise some start does work, and the only question is which one.
3