Problem
You are given two integer arraysgas and cost.
gas[i] represents the amount of gas available at station i, while cost[i] represents the amount of gas required to travel from station i to the next station.
Return the index of the gas station from which you can start and complete the entire circular journey. If no such starting station exists, return
-1.
You start with an empty tank, and the gas collected at a station can be used to travel to the next station.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]Output
3Solution
This problem can be solved using a Greedy Approach.First, if the total amount of gas is less than the total travel cost, completing the circuit is impossible. Therefore, we can immediately return
-1.
We then maintain the amount of gas remaining in the tank using
currentGas. If the current gas becomes negative at station i, it means the current starting station cannot reach the next station.
More importantly, none of the stations between the current starting station and
i can be a valid starting point either. Therefore, we can start from i + 1 and reset the current gas to 0.
If the total gas is sufficient to cover the total cost, the remaining candidate starting station is guaranteed to complete the circuit.
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int totalGas = 0;
int totalCost = 0;
int currentGas = 0;
int start = 0;
for (int i = 0; i < gas.length; i++) {
totalGas += gas[i];
totalCost += cost[i];
currentGas += gas[i] - cost[i];
// Current starting station cannot reach the next station.
if (currentGas < 0) {
start = i + 1;
currentGas = 0;
}
}
// Not enough gas to complete the circuit.
if (totalGas < totalCost) {
return -1;
}
return start;
}
}
Complexity
The array is traversed once, resulting inO(n) time complexity, and only a constant number of variables is used, resulting in O(1) space complexity.