Description
There are n gas stations along a circular route, where gas[i] is the amount of gas at station i. You have a car with unlimited tank that costs cost[i] of gas to travel to the next station. Return the starting gas station's index if you can travel around the circuit once clockwise, otherwise return -1.
Examples
Input:
gas = [1,2,3,4,5], cost = [3,4,5,1,2]Output:
3Explanation:
Starting at station 3, you can complete the circuit.
Input:
gas = [2,3,4], cost = [3,4,3]Output:
-1Explanation:
No starting station allows completing the circuit.
Input:
gas = [5,1,2,3,4], cost = [4,4,1,5,1]Output:
4Explanation:
Starting at station 4: tank=4, travel to station 0 (cost 1, tank=3+5=8), travel to station 1 (cost 4, tank=4+1=5), travel to station 2 (cost 4, tank=1+2=3), travel to station 3 (cost 1, tank=2+3=5), travel back to station 4 (cost 5, tank=0). Circuit completed successfully.
Constraints
- •
n == gas.length == cost.length - •
1 ≤ n ≤ 10⁵ - •
0 ≤ gas[i], cost[i] ≤ 10⁴