Gas Station
There are n gas stations along a circular route. You are given two integer arrays gas and cost where:
gas[i]is the amount of gas at theithstation.cost[i]is the amount of gas needed to travel from theithstation to the(i + 1)thstation. (The last station is connected to the first station)
You have a car that can store an unlimited amount of gas, but you begin the journey with an empty tank at one of the gas stations.
Return the starting gas station's index such that you can travel around the circuit once in the clockwise direction. If it's impossible, then return -1.
It's guaranteed that at most one solution exists.
Example 1:
Input: gas = [1,2,3,4], cost = [2,2,4,1]
Output: 3Explanation: Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 1 + 1 = 4
Travel to station 1. Your tank = 4 - 2 + 2 = 4
Travel to station 2. Your tank = 4 - 2 + 3 = 5
Travel to station 3. Your tank = 5 - 4 + 4 = 5
Example 2:
Input: gas = [1,2,3], cost = [2,3,2]
Output: -1Explanation:
You can't start at station 0 or 1, since there isn't enough gas to travel to the next station.
If you start at station 2, you can move to station 0, and then station 1.
At station 1 your tank = 0 + 3 - 2 + 1 - 2 = 0.
You're stuck at station 1, so you can't travel around the circuit.
Constraints:
1 <= gas.length == cost.length <= 10000 <= gas[i], cost[i] <= 1000
Recommended Time & Space Complexity
You should aim for a solution with O(n) time and O(1) space, where n is the size of the input array.
Hint 1
A brute force approach would be to start at each gas station, simulate the process, and return the index where completing the circuit is possible. This would be an O(n^2) time solution. Can you think of a better way? Maybe a greedy approach works.
Hint 2
We can immediately return -1 if sum(gas) < sum(cost), as completing the circuit is impossible due to insufficient gas. Otherwise, a solution always exists because the total gas is sufficient to cover the total cost, meaning there must be a valid starting point that allows completing the circuit.
Hint 3
We start with a variable total to track the gas balance and initialize the result index to 0. As we iterate through the array with index i, we accumulate the difference (gas[i] - cost[i]). If total becomes negative at any index, we reset it to 0 and update the result index to (i + 1).