Cyclic Gas Station Refill Loop
Problem
Stations sit on a circular route. At station i you pick up gas[i] units; the leg from i to i+1 burns cost[i] units. Find any starting index from which you can drive once around without ever running negative, or report that no such start exists. Insight: if total gas covers total cost, a solution exists. As you sweep, whenever the running tank goes negative, no station from the current candidate up to i can be the start — reset start to i + 1.
Input
gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]Output
3From index 3: tank runs 3, 7, 5, 4, 2 — never negative. From any earlier start, the tank dips below zero.
def can_complete_circuit(gas, cost):
total = tank = 0
start = 0
for i in range(len(gas)):
diff = gas[i] - cost[i]
total += diff
tank += diff
if tank < 0:
start = i + 1
tank = 0
return start if total >= 0 else -1function canCompleteCircuit(gas, cost) {
let total = 0, tank = 0, start = 0;
for (let i = 0; i < gas.length; i++) {
const diff = gas[i] - cost[i];
total += diff;
tank += diff;
if (tank < 0) { start = i + 1; tank = 0; }
}
return total >= 0 ? start : -1;
}class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int total = 0, tank = 0, start = 0;
for (int i = 0; i < gas.length; i++) {
int diff = gas[i] - cost[i];
total += diff;
tank += diff;
if (tank < 0) { start = i + 1; tank = 0; }
}
return total >= 0 ? start : -1;
}
}int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int total = 0, tank = 0, start = 0;
for (int i = 0; i < (int)gas.size(); i++) {
int diff = gas[i] - cost[i];
total += diff;
tank += diff;
if (tank < 0) { start = i + 1; tank = 0; }
}
return total >= 0 ? start : -1;
}