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 and fill up with gas[3] = 4, so tank = 4.
Travel from station 3 to station 0, spending cost[3] = 1, then fill gas[0] = 1, so tank = 4 - 1 + 1 = 4.
Travel from station 0 to station 1, spending cost[0] = 2, then fill gas[1] = 2, so tank = 4 - 2 + 2 = 4.
Travel from station 1 to station 2, spending cost[1] = 2, then fill gas[2] = 3, so tank = 4 - 2 + 3 = 5.
Travel from station 2 back to station 3, spending cost[2] = 4, so tank = 5 - 4 = 1.
The circuit is complete, so return 3.
Example 2:
Input: gas = [1,2,3], cost = [2,3,2]
Output: -1Explanation:
You cannot start at station 0 or 1 because neither has enough gas to travel to the next station.
If you start at station 2, fill gas[2] = 3, so tank = 3.
Travel from station 2 to station 0, spending cost[2] = 2, then fill gas[0] = 1, so tank = 3 - 2 + 1 = 2.
Travel from station 0 to station 1, spending cost[0] = 2, then fill gas[1] = 2, so tank = 2 - 2 + 2 = 2.
To travel from station 1 to station 2, you need cost[1] = 3 gas, but the tank only has 2.
So no starting station can complete the circuit, and the answer is -1.
Constraints:
1 <= gas.length == cost.length <= 10000 <= gas[i], cost[i] <= 1000
Topics
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).