Problem overview
There are n stations on a circular route. Station i has 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 the station you choose. At every 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(int[] gas, int[] cost) 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.
For gas = [1, 2, 3, 4, 5] and cost = [3, 4, 5, 1, 2] the answer is 3. Starting there, the tank holds 4, then 8 after the next station, then 7, 6 and 5, and the last stretch costs exactly 5. For gas = [2, 3, 4] and cost = [3, 4, 3] the answer is -1: the stations hold 9 units in all and the trip costs 10.
Approach: skip every start that fails
The brute-force way tries each station as the start and drives the whole circle, which is O(n²). The statement asks for O(n) time and O(1) extra space, so a start has to be ruled out without driving the circle again.
The greedy solution has two parts.
First, a feasibility check. 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. Otherwise a start exists.
Second, find it in one drive. Drive once from station 0 to the last station, keeping the gas in the tank and a candidate start, first 0. When the tank drops below 0 on the stretch after station i, the car could not have driven it. Then no station from the candidate up to i can be the start either: from the candidate the car reached each of them with 0 or more gas, and starting at one of them means being there with an empty tank, which is never better. So the candidate moves to i + 1 and the tank restarts at 0.
The last candidate works because of the first check. From it, the car reaches the end of the list without running dry. Each stretch it skipped loses gas overall, but the total isn't negative, so the gas left at the end covers everything those stretches lose, and the car gets around the circle back to its start.
A trace
For the first example, the second loop prints this after each station (tank is the gas on arriving at the next station, after any reset):
i=0 tank=0 start=1
i=1 tank=0 start=2
i=2 tank=0 start=3
i=3 tank=3 start=3
i=4 tank=6 start=3
At stations 0, 1 and 2 the tank goes negative (-2, -2 and -2, then resets), so the start moves to 3. From there it never drops again, and the function returns 3.
Step by step
- Store the number of stations,
gas.length, inn. The route is a circle, so aftern - 1comes 0. - Create
total, set to 0. It adds up what you take minus what you spend, over all stations. - Loop over all stations and add
gas[i] - cost[i]tototal. - If
total < 0, return -1. Otherwise a start exists and the second loop finds it. - Create
start, set to 0. It is the station being tried. Station 0 goes first, and the start moves forward only when it fails. - Create
tank, set to 0. The car starts with an empty tank. - Loop over the stations once more. One drive from station 0 to the last is enough.
- Add
gas[i] - cost[i]totank. Afterwardstankis the gas left on arriving at the next station. - If
tank < 0, the stretch couldn't be driven. Exactly 0 is fine: the car arrives empty and can still take the next station's gas. - Move
starttoi + 1and resettankto 0, since the trip now begins again at the new start. - After the loop, return
start.
The solution in Java
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int n = gas.length;
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 Java details worth a closer look:
gas.lengthis a field. An array's size is read without parentheses, unlikeString.length().- Two loops, two variables named
i. The loop variable is scoped to its ownforstatement, so the second loop can reuse the name. intis enough. Withnup to 100,000 and values up to 10,000, the sums never pass 1,000,000,000, within the range of anint(about 2.1 billion). Withn = 100000stations of 10000 gas and 0 cost, the code still returns 0.- No wrap-around code. The second loop never goes past station
n - 1. The first loop's check is what makes that safe: it proves the car has enough gas to cover the skipped stretches.
Complexity
Time: O(n). Two passes over the stations, with constant work at each.
Space: O(1). Only the integers n, total, start and tank are kept.
Edge cases and common mistakes
- One station.
gas = [5],cost = [4]returns 0. Withgas = [4]andcost = [5]it returns -1. - A tank of exactly zero.
gas = [3],cost = [3]returns 0. Testingtank <= 0instead oftank < 0would wrongly skip such a start. - All zeros.
gas = [0, 0]andcost = [0, 0]returns 0: the total is 0, which isn't negative, and the tank never drops below 0. - Leaving out the total check. Without it, the second loop would return some candidate even when no start works. For
gas = [4]andcost = [5]the loop alone would return 1, a station that doesn't exist. - Not resetting
tank. The negative gas from the failed start would carry over and spoil the new candidate. - Moving
starttoiinstead ofi + 1. Stationiis where the car just ran dry on the stretch after it, so it can't be the start.
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 = [2, 0],cost = [1, 1]gives0.gas = [5],cost = [4]gives0.gas = [4],cost = [5]gives-1.
