Gas station loop
Gas stations sit on a loop road, numbered 0 to n - 1. Station i holds gas[i] liters of gas. Driving from station i to the next station, one leg of the trip, uses cost[i] liters, and the station after n - 1 is station 0.
You pick a starting station and begin there with an empty tank that can hold any amount. At every station you reach, including the first, you take on all of its gas. The tank may never go below zero: you can leave station i only if, after taking on its gas, the tank holds at least cost[i] liters. Arriving at a station with exactly 0 liters is fine.
Return the starting station from which you can drive the whole loop, back to that same station. If no station works, return -1. If several stations work, return the smallest number.
gas = [1, 5, 3, 2], cost = [3, 2, 2, 3]Output1From station 1 the tank holds 3, 4, 3 and 1 liters after the four legs. Station 0 fails at once: 1 liter cannot cover a leg of 3.
gas = [2, 2, 2], cost = [3, 2, 2]Output-1The loop needs 7 liters in all, and the stations hold only 6.
gas = [3, 1, 2], cost = [2, 2, 2]Output0From station 0 the tank holds 1, 0 and 0 liters after the legs, never below zero. Station 2 works too, and 0 is smaller.
n == len(gas) == len(cost), 1 ≤ n ≤ 1050 ≤ gas[i], cost[i] ≤ 104
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.