There are n gas stations arranged in a circle, where gas[i] is the amount of fuel at station i and cost[i] is the fuel needed to travel from station i to station i+1. Return the starting station index from which you can travel around the circuit once in the clockwise direction, or -1 if it is impossible. Pattern focus: Greedy Choice Property. If the current starting point fails, every station between the start and the failure point can be skipped because none of them can do better as a start.
gas = fuel available at stations, cost = travel cost to next station
starting station index, or -1 if no solution
Example 1:
Input:
gas = [1,2,3,4,5] cost = [3,4,5,1,2]
Output:
3
Explanation:
Starting at index 3 lets you complete the full circuit.
Example 2:
Input:
gas = [2,3,4] cost = [3,4,3]
Output:
-1
Explanation:
Total fuel is less than total cost, so the trip is impossible.
Example 3:
Input:
gas = [5,1,2,3,4] cost = [4,4,1,5,1]
Output:
4
Explanation:
Starting from station 4 is feasible; earlier starts fail before completing the circle.