🎨Now live: Try our Free AI Image Generation Feature

Intuition
To solve this problem, we need to determine if there exists a starting gas station from which we can complete the entire circular route without running out of gas. The key insight is that if the total amount of gas is greater than or equal to the total cost, then a solution must exist. Additionally, if we fail to complete the journey from a certain starting point, it means that any starting point between that failed point and our current position is also invalid.
Approach
- Initialize Variables:
-
total
to track the total net gas (total gas - total cost). -cur
to track the current net gas from the current starting point. -start
to record the starting index. - Iterate Through the Gas Stations:
- For each gas station, calculate the net gas by subtracting
cost[i]
fromgas[i]
. - Add this net gas to bothtotal
andcur
. - Ifcur
becomes negative, it means we cannot complete the journey starting from the currentstart
. So, we updatestart
toi + 1
and resetcur
to 0. - Determine the Result:
- After iterating through all gas stations, if
total
is negative, return-1
because it is impossible to complete the circuit. - Otherwise, returnstart
as the valid starting index.
Complexity
- Time Complexity: O(n), where n is the number of gas stations. We only make a single pass through the gas and cost arrays.
- Space Complexity: O(1), as we only use a few extra variables for the computation.
Code
C++
class Solution {
public:
int canCompleteCircuit(vector& gas, vector& cost) {
int total = 0;
int cur = 0;
int start = 0;
for (int i = 0; i < gas.size(); i++) {
int netCost = gas[i] - cost[i];
total += netCost;
cur += netCost;
if (cur < 0) {
start = i + 1;
cur = 0;
}
}
return total < 0 ? -1 : start;
}
};
Python
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
total = 0
cur = 0
start = 0
for i in range(len(gas)):
netCost = gas[i] - cost[i]
total += netCost
cur += netCost
if cur < 0:
start = i + 1
cur = 0
return -1 if total < 0 else start
Java
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int total = 0;
int cur = 0;
int start = 0;
for (int i = 0; i < gas.length; i++) {
int netCost = gas[i] - cost[i];
total += netCost;
cur += netCost;
if (cur < 0) {
start = i + 1;
cur = 0;
}
}
return total < 0 ? -1 : start;
}
}
JavaScript
/**
* @param {number[]} gas
* @param {number[]} cost
* @return {number}
*/
var canCompleteCircuit = function(gas, cost) {
let total = 0;
let cur = 0;
let start = 0;
for (let i = 0; i < gas.length; i++) {
const netCost = gas[i] - cost[i];
total += netCost;
cur += netCost;
if (cur < 0) {
start = i+1;
cur = 0;
}
}
return total < 0 ? -1 : start;
};