121. Gas Station
There are `n` gas stations along a circular route, where the amount of gas at station `i` is `gas[i]`. You have a car with an unlimited gas tank and it costs `cost[i]` of gas to travel from station `i` to station `i + 1` (the last station wraps around to station 0). Given two integer arrays `gas` and `cost`, return the starting station index if you can travel around the circuit once in the clockwise direction, or -1 if it is impossible. If a solution exists, it is guaranteed to be unique. For example, given gas = [1,2,3,4,5] and cost = [3,4,5,1,2], starting at station 3 lets you complete the circuit, so return 3.
Examples
Input: [1,2,3,4,5] [3,4,5,1,2]
Output: 3
Explanation: Starting at station 3: tank 0+4-1=3, station 4: 3+5-2=6, station 0: 6+1-3=4, station 1: 4+2-4=2, station 2: 2+3-5=0. Never negative.
Constraints
- n == gas.length == cost.length
- 1 <= n <= 10^5
- 0 <= gas[i], cost[i] <= 10^4
Run checks all cases above. Submit evaluates all test cases.