1. Feasibility sum
total sums every gas - cost; non-negative means a solution exists.
let total = 0Typorithm · medium
Gas Station
▷ Interactive algorithm labgas-stationgreedyrunning-sumreset-startgreedy-choice
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn Gas Station
Greedy
Track total feasibility and a resettable running tank; the answer is where the tank last reset.
You can start at any station and must drive a full loop, gaining gas[i] and paying cost[i].
If the total gas is at least the total cost, exactly one valid start exists.
Whenever the running tank dips below zero, every station up to here fails, so the next station becomes the candidate start.
Preparing algorithm lab…
01
total >= 0 decides if any start works.
02
Reset start when tank < 0.
03
Single pass, no nested retries.
function canCompleteCircuit(gas, cost) {
let total = 0;
let tank = 0;
let start = 0;
for (let i = 0; i < gas.length; i += 1) {
const diff = gas[i] - cost[i];
total += diff;
tank += diff;
if (tank < 0) {
start = i + 1;
tank = 0;
}
}
return total >= 0 ? start : -1;
}Read the implementation
Connect each part of the code to the concept before you type.
2. Running tank
tank is the fuel since the current candidate start.
let tank = 03. Net at station
The net fuel gained or lost at station i.
const diff = gas[i] - cost[i]4. Reset start
If the tank goes negative, no start in [start..i] works; jump start to i + 1.
if (tank < 0)5. Final answer
A valid start exists iff the overall total is non-negative.
return total >= 0 ? start : -1A complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.