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 comes station 0 again. The tank has no size limit and starts empty. 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 canCompleteCircuit(gas, cost) 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.
For gas = [1, 2, 3, 4, 5] and cost = [3, 4, 5, 1, 2] the answer is 3. Starting there you take 4, and the tank holds 8 after station 4, then 7, 6 and 5 at stations 0, 1 and 2. The last stretch, back to station 3, costs 5, which is exactly what is in the tank. For gas = [2, 3, 4] and cost = [3, 4, 3] the answer is -1: there are 9 units of gas in all and the trip costs 10.
Approach: one pass with a moving start
The brute force tries every start and simulates the whole trip, which takes O(n²). The statement asks for O(n) time and O(1) extra space, so something smarter is needed. Two observations do it.
First, the totals. Add up gas[i] - cost[i] over all stations. If the total is negative, the trip costs more than all the gas there is, and no start can work. If it isn't negative, a start exists.
Second, a failed start rules out everything before the failure. Drive from the candidate start, starting at station 0, and keep the gas in tank. If the tank drops below 0 on the stretch after station i, the car can't have driven it. Now take any station between start and i. Starting from the original start, the car reached it with 0 or more gas. Starting there means arriving with an empty tank, which is never better, so the tank would still drop below 0 after station i. None of those stations can be the start, so the next candidate is i + 1 and the tank begins again from empty.
At the end, the last candidate is the answer. From it the car reaches the end of the list without running dry. The stretches skipped earlier each lose gas overall, but the grand total isn't negative, so the gas left at the end covers them. Inside a skipped stretch the tank goes below 0 only at its very end, so with that gas the car gets through each of them and back to the start.
For gas = [5, 1, 2, 3, 4] and cost = [4, 4, 1, 5, 1], the second loop goes like this:
i=0 tank=1 start=0
i=1 tank=0 start=2
i=2 tank=1 start=2
i=3 tank=0 start=4
i=4 tank=3 start=4
At i = 1 the tank would be -2, so the candidate moves to station 2 and the tank resets to 0. At i = 3 the tank would be -3, so the candidate moves to station 4. The answer is 4.
Step by step
- Store the number of stations in
n. The route is a circle, but the loops only walk from 0 ton - 1. - Declare
totalwithlet, at 0. It sums what each station gives minus what the stretch after it costs. - Loop over all stations and add
gas[i] - cost[i]tototal. - If
totalis negative, return -1. The gas can't pay for the whole trip. - Declare
startat 0, the station being tried. It moves forward only when it fails. - Declare
tankat 0, the gas left while driving fromstart. - Loop over the stations once more. One drive from station 0 to the end is enough.
- Take station
i's gas and drive its stretch: addgas[i] - cost[i]totank. Afterwardstankis the gas left on arriving at the next station. - Check for a dry tank: if
tank < 0, the car couldn't have driven the stretch fromstart. A tank of exactly 0 is fine, because the next station's gas can still be taken. - Move
starttoi + 1, the station after the failed stretch, which is the key step. - Empty the tank by setting it to 0, since the trip begins again at the new start.
- Return
start. The first loop showed that a start exists and the second loop skipped everything that can't be it.
The solution in TypeScript
class Solution {
canCompleteCircuit(gas: number[], cost: number[]): number {
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;
}
}
A few TypeScript details:
letandconst.nnever changes, so it is aconst.total,startandtankchange in the loops, so they arelet. Their types,number, are inferred from the starting 0.- Numbers are doubles. The sums stay far below 2^53 (at most 10^5 stations of at most 10^4 each), so every addition is exact and there is no overflow.
- Can
startbecomen? It can't whentotalisn't negative: if the tank were negative at the last station, every stretch since the previous reset would be negative, and so would the total. So the returned index is always a valid station.
Complexity
Time: O(n). Two passes over the stations, each doing constant work per station.
Space: O(1). The method keeps four numbers: n, total, start and tank.
Edge cases and common mistakes
- Skipping the total check. The loop would still return some station, but not -1. For
gas = [2, 3, 4]andcost = [3, 4, 3]it returns 2 instead of -1, because the loop on its own can't see the stretches that wrap around the circle. - Treating 0 as failure. Use
tank < 0, nottank <= 0. A tank of exactly 0 after a stretch is allowed: the car arrives with an empty tank and takes the next station's gas. - Resetting
starttoi. The failed stretch is the one after stationi, so the car can't leave stationieither, which makesi + 1the next candidate. - Forgetting to reset
tank. The new start begins with an empty tank, and leftover debt from the old start would count against it. - One station.
gas = [5]withcost = [4]returns 0, andgas = [4]withcost = [5]returns -1.
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 = [3],cost = [3]gives0.
