mediumGreedy
Gas Station
## Problem
There are `n` gas stations along a circular route, where the amount of gas at the `i`th station is `gas[i]`.
You have a car with an unlimited gas tank and it costs `cost[i]` of gas to travel from the `i`th station to its next `(i + 1)`th station. You begin the journey with an empty tank at one of the gas stations.
Given two integer arrays `gas` and `cost`, return *the starting gas station's index* if you can travel around the circuit once in the clockwise direction, otherwise return `-1`. If there exists a solution, it is **guaranteed to be unique**.
There are `n` gas stations along a circular route, where the amount of gas at the `i`th station is `gas[i]`.
You have a car with an unlimited gas tank and it costs `cost[i]` of gas to travel from the `i`th station to its next `(i + 1)`th station. You begin the journey with an empty tank at one of the gas stations.
Given two integer arrays `gas` and `cost`, return *the starting gas station's index* if you can travel around the circuit once in the clockwise direction, otherwise return `-1`. If there exists a solution, it is **guaranteed to be unique**.
Examples
Input
gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output
3
Start at station 3. 4-1=3, 3+5-2=6, 6+1-3=4, 4+2-4=2, 2+3-5=0.
Input
gas = [2,3,4], cost = [3,4,3]
Output
-1
Total gas (9) < total cost (10). Impossible.
Constraints
n == gas.length == cost.length
1 <= n <= 10^5
0 <= gas[i], cost[i] <= 10^4
Python
Loading...