Problem overview
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 costs cost[i]. After station n - 1 the route continues at station 0. The tank has no size limit and starts empty. At each station you take all its gas and then drive on. A stretch can be driven only if the tank holds at least its cost.
The function can_complete_circuit returns the index of the station to start from so that you complete one full circle, or -1 if no start works. When a start works, it is the only one.
In the first example, gas = [1, 2, 3, 4, 5] and cost = [3, 4, 5, 1, 2]. Starting at station 3 gives a tank of 4, then 8 after station 4, then 7, 6 and 5 at stations 0, 1 and 2, and the last stretch back to station 3 costs exactly 5. The answer is 3.
Approach: skip the stations that can't be the start
The brute force tries every start and simulates the whole circle, which costs O(n²). The lesson does it in one pass with two observations.
The total decides whether a start exists. Add up gas[i] - cost[i] over all stations. If the total is negative, the trip around costs more than all the gas available, and no start works. The second example is like that: the stations hold 2 + 3 + 4 = 9 units and the circle costs 3 + 4 + 3 = 10. If the total is not negative, a start exists.
A failure rules out a whole stretch. Drive from a candidate start, keeping the tank. If the tank drops below 0 after station i, the car couldn't have driven that stretch from start. Now consider any station between start and i. Starting at the candidate, 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 go negative by i. None of those stations can be the start, and the next candidate is i + 1 with an empty tank.
When the pass ends, the last candidate is the answer. From it the car reaches the end of the list without running dry. Each stretch skipped before it lost gas overall, but the grand total isn't negative, so the gas left at the end covers everything the skipped stretches lost. Inside a skipped stretch the tank only went negative at its very end, so with that spare gas the car also gets through each of them and back to the start.
Here is the pass for the third example, gas = [5, 1, 2, 3, 4] and cost = [4, 4, 1, 5, 1]:
i=0 tank=1
i=1 tank=-2 -> start=2, tank=0
i=2 tank=1
i=3 tank=-1 -> start=4, tank=0
i=4 tank=3
The pass ends with start = 4, which is the answer.
Step by step
- Store the number of stations in
nwithgas.len(). The route is a circle, but the code never wraps around: one pass over the list is enough. - Create
totalas a mutable variable at 0. It sums what each station gives minus what the stretch after it costs. - Loop over the stations with
iover0..n. - Add
gas[i] - cost[i]tototalwith+=. It is negative for a station that gives less than the next stretch costs. - Return -1 when
totalis negative. Otherwise a start exists and the second loop finds it. - Create
start, mutable, at 0. Station 0 is tried first, and the candidate moves only when it fails. - Create
tank, mutable, at 0: the gas in the tank when driving fromstart. - Loop over the stations again with
iover0..n. A single drive from station 0 to the last station is enough. - Add
gas[i] - cost[i]totank. Afterwards,tankis the gas left on arriving at the next station. - Check whether
tankis negative. Exactly 0 is fine: the car arrives empty and can still take the next station's gas. - Move
starttoi + 1. This is the key step: no station from the old start toican be the start. - Reset
tankto 0, because the trip now begins again at the new start. - Return
start as i32. The index is ausizeand the function returns ani32.
The solution in Rust
impl Solution {
fn can_complete_circuit(gas: Vec<i32>, cost: Vec<i32>) -> i32 {
let n = gas.len();
let mut total = 0;
for i in 0..n {
total += gas[i] - cost[i];
}
if total < 0 {
return -1;
}
let mut start = 0;
let mut tank = 0;
for i in 0..n {
tank += gas[i] - cost[i];
if tank < 0 {
start = i + 1;
tank = 0;
}
}
start as i32
}
}
The Rust details worth a closer look:
- Inferred types.
totalandtankstart as the literal0and becomei32because they are added togas[i] - cost[i], which is ani32. The values are at most 10,000 each and there are at most 100,000 stations, so the sums stay far from thei32limits. startis ausize. Assigningi + 1to it makes the compiler inferusize, which is why the function ends withstart as i32. The cast is a plain conversion here: the value is at mostn, far belowi32::MAX.startcan becomen. If the last stretch fails,startis set ton, one past the last station. That can't be returned, because the total check already guaranteed that the stretches can't all fail at the end: when the total is not negative, the last candidate is a real station.- Early
return.return -1;leaves the function at once. The final line,start as i32, has no semicolon and is the value returned otherwise. - Indexing.
gas[i]panics wheniis out of bounds, but both loops stop atn, and the lesson's inputs have equal lengths forgasandcost.
Complexity
Time: O(n). There are two simple passes over the stations, and each step does a few additions and one comparison.
Space: O(1). The code keeps four variables, n, total, start and tank, however long the input is.
Edge cases and common mistakes
- A single station.
gas = [5]andcost = [4]returns 0, andgas = [4]withcost = [5]returns -1, because the total is -1. - A tank of exactly zero. The check is
tank < 0. Usingtank <= 0would reject a start that arrives at the next station with exactly 0 and could continue. Forgas = [3, 1, 1]andcost = [1, 2, 2]the tank is 2, 1, 0 and the answer is 0; with<=the last step would movestartpast the end. - Skipping the total check. Without it, the second loop still ends with some
start, so the second example would return 2 instead of -1. The total check is what makes the last candidate trustworthy. - Restarting at
iinstead ofi + 1. Stationiis where the tank ran dry on the stretch after it, so it can't be the start either. - Forgetting to reset the tank. A negative
tankcarried into the new trip would make every later station look worse than it is. - Everything zero. With
gas = [0, 0]andcost = [0, 0]every start works, which the lesson excludes, but the code returns 0.
Testing
gas = [1, 2, 3, 4, 5],cost = [3, 4, 5, 1, 2]gives 3.gas = [2, 3, 4],cost = [3, 4, 3]gives -1.gas = [5, 1, 2, 3, 4],cost = [4, 4, 1, 5, 1]gives 4.gas = [5],cost = [4]gives 0.gas = [4],cost = [5]gives -1.gas = [3, 1, 1],cost = [1, 2, 2]gives 0.
