Problem overview
The method canCompleteCircuit(gas, cost) describes n gas stations on a circular route. Station i gives gas[i] units of gas, and driving from station i to the next one costs cost[i]. After station n - 1 the route continues at station 0. The tank has no size limit and starts empty at the station you choose. At each station you take all its gas, then drive on, and you can drive a stretch only if the tank holds at least its cost.
The method returns the index of the station to start from so that you drive once around the circle and get back to it, or -1 if no start works. At most one start works.
In the first example, gas = [1, 2, 3, 4, 5] and cost = [3, 4, 5, 1, 2], the answer is 3. Starting at station 3 the tank holds 4, then 8 at station 4, 7 at station 0, 6 at station 1 and 5 at station 2, and the last stretch costs exactly 5. In the second example, gas = [2, 3, 4] and cost = [3, 4, 3], the stations hold 9 units of gas but the trip costs 10, so the answer is -1.
Approach: skip every start that fails
The brute force tries every start and simulates the full circle, which is O(n²). The lesson does it in one pass in O(n) time and O(1) extra space, with two ideas.
First, check that a start can exist at all. Add up gas[i] - cost[i] over all the stations. If the total is negative, the trip costs more than all the gas there is, and no start can work. Return -1 at once.
Second, find the start by driving once from station 0. Keep a candidate start, first 0, and a tank that holds the gas since that candidate. At each station add gas[i] - cost[i]. If the tank drops below 0, the car could not have driven the stretch after station i from start. Then move the candidate to station i + 1 and empty the tank.
Skipping all the stations from the old start to i is safe. Starting at start, the car reached each of them with 0 or more gas. Starting at one of them means being there with an empty tank, which is never better, so the tank would still drop below 0 after station i. None of them can be the start.
The last candidate works because the total isn't negative. Each stretch skipped before it loses gas overall, but the gas left in the tank at the end is at least what those stretches lose together. Inside a skipped stretch the tank only goes below 0 at its very end, so with that leftover gas the car gets through each stretch and back to the start.
Here is the pass over the first example. Each line shows the station, gas[i] - cost[i], the tank afterwards and the candidate:
i 0 diff -2 tank 0 start 1 (reset)
i 1 diff -2 tank 0 start 2 (reset)
i 2 diff -2 tank 0 start 3 (reset)
i 3 diff 3 tank 3 start 3
i 4 diff 3 tank 6 start 3
The candidate ends at 3, the answer. For the third example, gas = [5, 1, 2, 3, 4] and cost = [4, 4, 1, 5, 1], the pass moves the candidate to 2, then to 4:
i 0 diff 1 tank 1 start 0
i 1 diff -3 tank 0 start 2 (reset)
i 2 diff 1 tank 1 start 2
i 3 diff -2 tank 0 start 4 (reset)
i 4 diff 3 tank 3 start 4
Step by step
- Store
n, the number of stations, asgas.length. - Declare
totalwithletand start it at 0. It adds up what each station gives minus what the stretch after it costs. - Loop over the stations, with
ifrom 0 whilei < n. - Add
gas[i] - cost[i]tototalwith+=. - Return -1 if
total < 0, right after the loop. Otherwise a start exists, and the second pass finds it. - Declare
startwithletand set it to 0. Station 0 is tried first, and the candidate moves only when it fails. - Declare
tankwithletand set it to 0: the car starts empty. - Loop over the stations again from 0 to
n - 1. A single drive is enough. - Take the gas and drive: add
gas[i] - cost[i]totank. Afterwardstankis the gas left on arriving at the next station. - Test
tank < 0. Exactly 0 is fine: the car arrives with an empty tank and can still take the next station's gas. - Inside the
if, movestarttoi + 1, the station after the stretch where the tank ran dry. - Empty the tank by setting it to 0, because the trip begins again at the new start.
- Return
startafter the loop.
The solution in JavaScript
class Solution {
canCompleteCircuit(gas, cost) {
const n = gas.length;
let total = 0;
for (let i = 0; i < n; i++) {
total += gas[i] - cost[i];
}
if (total < 0) {
return -1;
}
let start = 0;
let tank = 0;
for (let i = 0; i < n; i++) {
tank += gas[i] - cost[i];
if (tank < 0) {
start = i + 1;
tank = 0;
}
}
return start;
}
}
The JavaScript details worth knowing:
constandlet.nnever changes, so it isconst.total,startandtankchange in the loops, so they uselet.- The circle is never wrapped. There is no
% nanywhere. The total check already guarantees that the stretches before the candidate are covered by the leftover gas, so one pass over the list is enough. - Two passes, still
O(n). The method makes two separate loops over the stations, each with constant work per element. The time is about2nsteps, which isO(n). - Plain numbers. The values are at most 10,000 and there are at most 100,000 stations, so sums stay far below the point where JavaScript numbers stop being exact. The statement guarantees no overflow can matter.
- Can
startreachn? Only if the tank is negative after the last station, which would maketotalnegative too. That case returned -1 earlier, so the method never returns an index past the end.
Complexity
Time: O(n). Two passes over the stations, each doing a constant amount of work per station.
Space: O(1). Four numbers (n, total, start and tank) and the loop index, however many stations there are.
Edge cases and common mistakes
- One station.
gas = [5],cost = [4]returns 0.gas = [4],cost = [5]returns -1.gas = [3],cost = [3]returns 0, because arriving with exactly zero left is allowed. - Total gas less than total cost. The first loop catches it. Without that check, the second loop would return a candidate that does not work.
- Using
tank <= 0. An empty tank is fine, so with<=the candidate would skip stations that work. Forgas = [3]andcost = [3]the answer would move to 1, past the end of the list. - Forgetting to reset the tank. Carrying the negative value into the new candidate makes it look worse than it is.
- Zero gas and zero cost.
gas = [0, 0],cost = [0, 0]returns 0: nothing is ever spent, so the first station works. (The statement guarantees at most one working start, so inputs like this one are outside it, but the code is still safe on them.)
Testing
gas = [1, 2, 3, 4, 5],cost = [3, 4, 5, 1, 2]gives3.gas = [2, 3, 4],cost = [3, 4, 3]gives-1.gas = [5, 1, 2, 3, 4],cost = [4, 4, 1, 5, 1]gives4.gas = [5],cost = [4]gives0.gas = [4],cost = [5]gives-1.
