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 a stretch can be driven only if the tank holds at least its cost.
The function canCompleteCircuit returns the station to start from so that you get all the way around and back, 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 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, which is exactly the cost of the last stretch back to station 3. For gas = [2, 3, 4] and cost = [3, 4, 3] the answer is -1: there are 9 units of gas for a trip that costs 10.
Approach: two facts make one pass enough
The direct way is to try every station as the start and simulate the whole circle, which costs O(n²). The statement asks for O(n) time and O(1) extra space, so the work has to be shared between starts. Two observations do that.
First, a total check. Add up gas[i] - cost[i] over all stations. If the sum is negative, there is less gas in the whole circle than the trip costs, so no start can work: return -1. If it is not negative, some start exists, and the next pass finds it.
Second, a failed start rules out everything it passed. Drive from a candidate start and keep the gas in tank. Whenever tank goes below 0 on the stretch after station i, the car could not have driven it. The candidate moves to i + 1 and the tank is emptied. Skipping every station from the old start to i is safe because 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 after station i.
The last candidate is the answer because of the total check. The stretches skipped before it each lose gas overall, but the grand total is not negative, so what the tank holds at the end covers all of those losses. Inside a skipped stretch the tank only goes below 0 at the very end of it, so with that extra gas the car gets through each of them and back to the start.
Here is the second pass on the first example, where the total check has already passed:
i=0 tank=-2 -> start=1, tank reset
i=1 tank=-2 -> start=2, tank reset
i=2 tank=-2 -> start=3, tank reset
i=3 tank=3
i=4 tank=6
start=3The 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 reset
i=2 tank=1
i=3 tank=-1 -> start=4, tank reset
i=4 tank=3
start=4Step by step
- Store the number of stations in an
intnamedn, fromgas.size(). - Create
total, anintset to 0. It adds up what each station gives minus what the stretch after it costs. - Loop over every station and add
gas[i] - cost[i]tototal. A station with less gas than its stretch costs adds a negative number. - If
totalis negative, return -1. All the gas cannot pay for the trip, whatever the start. - Create
start, set to 0, the station being tried. Station 0 goes first, and the start moves only when it fails. - Create
tank, set to 0: the gas on board when driving fromstart. - Loop over the stations once more from 0 to
n - 1. One drive to the end of the list is enough. - Add
gas[i] - cost[i]totank. Afterwardstankis the gas left on arriving at the next station. - If
tankis negative, the stretch could not be driven. Exactly 0 is fine: the car arrives empty and takes the next station's gas. - Move
starttoi + 1, the key step, and settankback to 0, because the trip now begins again at the new start. - Return
startafter the loop.
The solution in C++
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int n = gas.size();
int total = 0;
for (int i = 0; i < n; i++) {
total += gas[i] - cost[i];
}
if (total < 0) {
return -1;
}
int start = 0;
int tank = 0;
for (int i = 0; i < n; i++) {
tank += gas[i] - cost[i];
if (tank < 0) {
start = i + 1;
tank = 0;
}
}
return start;
}
};
The C++ details worth a closer look:
- The parameters are references.
vector<int>&means the function reads the caller's vectors directly, with no copy. That keeps the extra space atO(1). The function never changes them. int n = gas.size()converts the unsigned size toint. Withnat most 100,000 that is safe, and it keeps the loop comparisonsi < nbetween twointvalues.intis enough for the sums. Eachgas[i] - cost[i]is between -10,000 and 10,000, and a sum over 100,000 stations stays within 1,000,000,000, below the 32-bit limit of about 2.1 billion. Signed overflow would be undefined behaviour in C++, so it is worth checking that it cannot happen.- The return value is an index. It is 0-based, like the vectors, and -1 means no start exists.
Complexity
Time: O(n). There are two loops over the stations, each doing a constant amount of work per step.
Space: O(1). The code keeps only a handful of integers: n, total, start, tank and the loop counter.
Edge cases and common mistakes
- A single station.
gas = [5]withcost = [5]returns 0, since the tank holds exactly the cost. Withcost = [6]the total is negative and the function returns -1. - Dropping the total check. Without it, the second loop still ends with some
start. Forgas = [2, 3, 4]andcost = [3, 4, 3]the loop alone would return 2 for an impossible trip, instead of -1. - Treating an empty tank as failure. The test is
tank < 0, nottank <= 0. Arriving with exactly 0 is allowed, because the next station's gas is added before the next stretch is driven. - Forgetting to reset the tank. After moving
start, the new trip must begin empty. Keeping the negative balance would blame the new start for the old one's shortfall. - Moving
starttoiinstead ofi + 1. Stationiwas reached with 0 or more gas and still failed, so starting there with an empty tank cannot do better. The next candidate isi + 1. - Stations that give nothing. With all zeros,
gas = [0, 0]andcost = [0, 0], the tank is never negative and the function returns 0.
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 = [5]gives0.gas = [5],cost = [6]gives-1.gas = [3, 1, 1],cost = [1, 2, 2]gives0.
