110. Gas Station

Medium · Array

There are `n` gas stations arranged in a circle. You are given two integer arrays `gas` and `cost` where `gas[i]` is the amount of gas at station `i`, and `cost[i]` is the gas required to travel from station `i` to the next station `(i+1) % n`.

You have a car with an unlimited gas tank. Starting with an empty tank at one of the gas stations, find the starting station's index such that you can travel around the circuit once in the clockwise direction. If no such station exists, return `-1`.

It is guaranteed that if a solution exists, it is unique.

Examples

Example 1
Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Explanation: Start at station 3 (gas=4). Travel to station 4: tank = 4-1+5 = 8. Travel to station 0: tank = 8-2+1 = 7. Travel to station 1: tank = 7-3+2 = 6. Travel to station 2: tank = 6-4+3 = 5. Travel to station 3: tank = 5-5 = 0. You complete the circuit!
Example 2
Input: gas = [2,3,4], cost = [3,4,3]
Output: -1
Explanation: Total gas (9) equals total cost (10), so it is impossible to complete the circuit. Return -1.

Constraints