121. Gas Station

MediumGreedy

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
Loading...

Run checks all cases above. Submit evaluates all test cases.