Gas Station
Find the starting gas station to complete the circuit.
Examples
Stations 0, 1 and 2 each run dry at once; from station 3 the tank never drops below 0 on the full lap.
The route offers 9 gas but burns 10, so no start can finish.
Two stretches run dry, and the lap from the last station wraps past the end.
Problem Understanding
There are n gas stations on a circular route. Station i gives gas[i] units of gas, and driving from station i to the next one (from the last station back to station 0) burns cost[i].
The car starts with an empty tank at a station of your choosing. Return the index of that station if the car can drive round the whole circuit once, otherwise return -1. If a solution exists, it is guaranteed to be unique.
Strategy
One pass, adding each station’s net = gas[i] - cost[i] to two sums:
total_tank, the whole trip. If it ends below 0, the route burns more than it offers and no start can finish: return -1.curr_tank, the tank since the candidatestart. If it drops below 0 at stationi, no station fromstarttoican be the start, so setstart = i + 1and empty the tank.
If total_tank ends at 0 or more, start is the answer.
Interactive Visualization
The route drawn as the loop it is. Above each station is the gas it gives; on each arrow, what that leg burns. The candidate start is outlined and the legs driven since it are lit. When the tank runs dry the failing leg turns red and the stretch is greyed out — none of those stations can be the start.
Try Late start: two stretches run dry, the answer is the last station, and the lap it completes wraps past the end.
Dry Run
gas [1, 2, 3, 4, 5], cost [3, 4, 5, 1, 2]:
| i | gas - cost | net | whole trip | tank since start | action |
|---|---|---|---|---|---|
| 0 | 1 - 3 | -2 | -2 | -2 | ran dry: start = 1, tank = 0 |
| 1 | 2 - 4 | -2 | -4 | -2 | ran dry: start = 2, tank = 0 |
| 2 | 3 - 5 | -2 | -6 | -2 | ran dry: start = 3, tank = 0 |
| 3 | 4 - 1 | 3 | -3 | 3 | keep going |
| 4 | 5 - 2 | 3 | 0 | 6 | keep going |
The whole trip balances at 0, which is not below 0 — return 3.
Edge Cases & Common Mistakes
Check these conditions:
Not enough gas overall means -1, whatever the order. If sum(gas) < sum(cost), every start runs dry somewhere. The whole-trip balance makes that check in the same pass.
A dry tank rules out the whole stretch, not just its start. Every station from the start to the failing leg was reached with fuel to spare, so starting at one of them can only arrive with less.
No second lap is needed. When the whole-trip balance ends at 0 or more, the fuel banked from the start onward covers the stations before it.
More than one valid start? LeetCode guarantees at most one. On an input where several work, this returns the first — every earlier station sits in a stretch that ran dry.
Solution
One pass, two running tanks — the lines light up as the figure above steps.
Gas Station Code
1var canCompleteCircuit = function(gas, cost) {2 let totalTank = 0;3 let currTank = 0;4 let start = 0;5 for (let i = 0; i < gas.length; i++) {6 const net = gas[i] - cost[i];7 totalTank += net;8 currTank += net;9 if (currTank < 0) {10 start = i + 1;11 currTank = 0;12 }13 }14 return totalTank >= 0 ? start : -1;15};