Gas Station
MediumGreedy
There are n gas stations arranged in a circle, numbered 0 to n - 1. Station i provides gas[i] units of fuel, and driving from station i to the next station (i + 1, or 0 after the last one) uses cost[i] units.
Your car has an unlimited tank and starts empty at a station of your choice. At each station you first fill up with that station's gas[i], then drive to the next station. The tank may hit exactly 0 on arrival, but it can never go below 0 along the way.
Return the index of the station you should start from to drive all the way around the circle once, arriving back at the start. If it is impossible from every station, return -1. When a solution exists, it is guaranteed to be unique.
Example 1
- Input:
- gas = [3, 1, 4, 2], cost = [2, 4, 1, 3]
- Output:
- 2
- Explanation
- From station 2: fill 4, spend 1 (tank 3); fill 2, spend 3 (tank 2); fill 3, spend 2 (tank 3); fill 1, spend 4 (tank 0) and you are back at station 2. Every other start runs dry: for example, starting at station 0 you reach station 1 with 1 unit, fill up to 2, but need 4 to leave.
Example 2
- Input:
- gas = [2, 3, 4], cost = [3, 4, 3]
- Output:
- -1
- Explanation
- The stations offer 9 units of fuel in total but the full loop costs 10, so no starting point can work.
Example 3
- Input:
- gas = [5], cost = [5]
- Output:
- 0
- Explanation
- With one station you fill 5 units and spend all 5 driving around back to it. Ending at exactly 0 is allowed.
Constraints
n == gas.length == cost.length- 1 ≤
n≤ 105 - 0 ≤
gas[i],cost[i]≤ 104 - If a valid starting station exists, there is exactly one