Greedy The best choice now
493. Gas Station
There are n gas stations on a circular road, numbered from 0 to n - 1. Station i has gas[i] units of
gas, and driving from station i to the next station uses cost[i] units. The station after n - 1 is
station 0.
Your car's tank has no limit, and it starts empty. You pick a station to start from. At every station you
take all of its gas, then drive to the next one. Return the index of the station from which you can drive
once around the circle and get back to it. If no station works, return -1.
The tank must never go below zero between two stations. Arriving at a station with an empty tank is fine.
Example 1
Input: gas = [6, 7, 1, 3, 4], cost = [4, 7, 7, 1, 1]
3Explanation: From station 3, the tank holds 2 on arrival at station 4, then 5 at station 0, 7 at station 1, 7 at station 2, and 1 back at station 3. Every other start runs out of gas on the way.
Example 2
Input: gas = [3, 1, 2], cost = [2, 3, 3]
-1Explanation: The stations hold 6 units of gas in all, and one lap uses 8.
Example 3
Input: gas = [0, 1000000000, 0], cost = [1000000000, 0, 0]
1Explanation: From station 1 we take 109 units, and the last leg uses all of them. We arrive back at station 1 with an empty tank, which is allowed.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ n ≤ 105gas.length = cost.length = n0 ≤ gas[i], cost[i] ≤ 109- At most one station works as the start.
Clarifying questions
What you would ask an interviewer before writing any code.