Dare2Solve
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.
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:
cost[i]
from gas[i]
.total
and cur
.cur
becomes negative, it means we cannot complete the journey starting from the current start
. So, we update start
to i + 1
and reset cur
to 0.Determine the Result:
total
is negative, return -1
because it is impossible to complete the circuit.start
as the valid starting index.class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& 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;
}
};
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
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;
}
}
/**
* @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;
};