Gas Station
Understand the problem
There are n gas stations arranged in a circle. At station i you can fill up gas[i] fuel; driving from station i to the next one costs cost[i] fuel. The car starts with an empty tank. Return the index of the starting station that lets you complete one full lap, or -1 if it's impossible. The problem guarantees the answer (if there is one) is unique.
Example:
gas = [1, 2, 3, 4, 5]
cost = [3, 4, 5, 1, 2]
output = 3 // starting from station 3, you can complete the full circleShow the basic approach (slower)
O(n²) time, O(1) spacefunction canCompleteCircuit(gas: number[], cost: number[]): number {
const n = gas.length
for (let start = 0; start < n; start++) {
let tank = 0, ok = true
for (let step = 0; step < n; step++) {
const i = (start + step) % n
tank += gas[i] - cost[i]
if (tank < 0) { ok = false; break }
}
if (ok) return start
}
return -1
}Try each station as the starting point and simulate the full lap.
Correct but repeats a lot of work — each start re-runs almost the entire circle.
Optimal solution
O(n) time, O(1) spacefunction canCompleteCircuit(gas: number[], cost: number[]): number {
let total = 0 // net gas balance over the whole circuit
let tank = 0 // gas accumulated since the current start
let start = 0
for (let i = 0; i < gas.length; i++) {
const diff = gas[i] - cost[i]
total += diff
tank += diff
if (tank < 0) { // can't reach station i+1 from the current start
start = i + 1
tank = 0
}
}
return total >= 0 ? start : -1
}The optimal solution rests on two greedy observations:
- if total
gas< totalcost, there is definitely no solution. - If, driving from
start, the tank goes negative at stationi, then none of the stations in [start, i] can be the starting point — discard them all and retry fromi+1
One pass is enough since the answer (when it exists) is unique.
Step-by-step trace
1function canCompleteCircuit(gas: number[], cost: number[]): number {2 let total = 0 // net gas balance over the whole circuit3 let tank = 0 // gas accumulated since the current start4 let start = 05 for (let i = 0; i < gas.length; i++) {6 const diff = gas[i] - cost[i]7 total += diff8 tank += diff9 if (tank < 0) { // can't reach station i+1 from the current start10 start = i + 111 tank = 012 }13 }14 return total >= 0 ? start : -115}Edge cases to remember
Total gas < total cost →
total < 0→ return −1 even if the final tank happens to be positive.The last station makes the tank negative and start moves to n: thanks to the final
total >= 0check the result is still correct (when a solution exists, start never runs past the valid indices).gas = cost at every station → total = 0, every starting point works; the answer is the default start 0.
A single station with gas[0] ≥ cost[0] → return 0; otherwise return −1.