You get two arrays, gas and cost. They describe n gas stations on a circular road.
Station i has gas[i] units of gas. Driving from station i to the next one uses cost[i] units.
Return the station where a car can start and drive one full lap. If no station works, return -1.
The stations are numbered 0 to n - 1 in driving order. After station n - 1 comes station 0 again.
The car starts with an empty tank, and the tank has no limit. At each station, it takes all the gas. It can drive to the next station only if it has enough gas for that drive.
Example 1:
Input: gas = [3, 1, 4, 2], cost = [2, 3, 1, 3] Output: 2 Explanation: Start at station 2 and take its 4 units. Drive to station 3. Use 1, then take 2. The tank has 5. Drive to station 0. Use 3, then take 3. The tank has 5. Drive to station 1. Use 2, then take 1. The tank has 4. Drive back to station 2. Use 3. The tank still has 1. From station 0, 1 or 3, the tank runs dry before the lap ends.
Example 2:
Input: gas = [4, 2, 6], cost = [5, 4, 4] Output: -1 Explanation: All the gas adds up to 12 units. One lap uses 13.
Example 3:
Input: gas = [2], cost = [2] Output: 0 Explanation: There is only one station. The lap goes from station 0 back to itself. Its 2 units are exactly enough.
Constraints:
- 1 to 100,000 stations.
gasandcosthave one value per station.- Each value is a whole number from 0 to 10,000.
- At most one station works as the start.
Note:
Your algorithm should run in O(n) time and use O(1) extra space.
The tutorial is greedy. First it adds up gas[i] - cost[i] over all the stations: if the total is negative, the trip around costs more than all the gas there is, and no start can work. Otherwise it drives once from station 0 to the last station, keeping the gas in the tank and a candidate start, first 0. Whenever the tank drops below 0 on the stretch after station i, the car couldn't have driven it: the candidate moves to station i + 1, and the tank starts again from empty. At the end, the candidate is the answer.
Why skipping all the stations from start to i is safe: starting at start, the car reached each of them with 0 or more gas in the tank. Starting at one of them instead means being there with an empty tank, which is never better, so the tank would still drop below 0 after station i. None of them can be the start, and the next station to try is i + 1.
Why the last candidate works: from it, the car reaches the end of the list without running dry. Each stretch it skipped before it loses gas overall, but the total isn't negative, so the gas left in the tank at the end is at least what all of them lose together. Inside a skipped stretch the tank only goes below 0 at its very end, so with that gas the car gets through each of them, and back to the start.
Free plan: 30 tutor messages. PRO is unlimited.
