Problem overview
Stations 0 to n - 1 sit 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 the station you choose. At each station you take all its gas, then drive on, and you can only drive a stretch if the tank holds at least its cost.
The function canCompleteCircuit returns the index of the station to start from so that you complete one full lap, or -1 if no start works. At most one start works.
In gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2] the answer is 3. Starting there you take 4, drive to station 4 and take 5 (tank 8), and so on around the circle. The last stretch costs 5 and the tank holds exactly 5, which is enough. In gas = [2, 3, 4], cost = [3, 4, 3] there are 9 units of gas for a trip that costs 10, so the answer is -1.
Approach: two greedy facts
The direct way is to try every station as the start and simulate the lap, which is O(n²). For 100,000 stations that is too slow. The statement asks for O(n) time and O(1) extra space, and two observations deliver that.
Fact 1: the totals decide whether any start exists. Add up gas[i] - cost[i] over all stations. If the sum is negative, the lap costs more than all the gas available, and no start can work. If it isn't negative, a start exists.
Fact 2: a failure rules out every station before it. Drive once from station 0 to the last, keeping a candidate start (first 0) and the tank since that start. If the tank drops below 0 on the stretch after station i, the car couldn't have made it from start. Every station between start and i is ruled out too: the car reached each of them with 0 or more gas, and starting there would mean arriving with an empty tank, which is never better, so the tank would still go negative at i. The next candidate is i + 1, with an empty tank.
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 lose gas overall, but since the grand total isn't negative, the gas left in the tank at the end covers all those losses, and the car can wrap around to its starting point.
For gas = [1, 2, 3, 4, 5] and cost = [3, 4, 5, 1, 2], the second pass runs like this:
i=0 tank=-2 -> start=1
i=1 tank=-2 -> start=2
i=2 tank=-2 -> start=3
i=3 tank=3
i=4 tank=6
The first three stations each leave the tank at -2, so the candidate moves forward each time. From station 3 the tank stays positive, and the function returns 3.
Step by step
- Store the station count as
n := len(gas). - Declare
totalas 0. It will add up what you gain minus what you spend over all stations. - Loop over every station with
ifrom 0 ton - 1. - Add
gas[i] - cost[i]tototal. A station whose gas is less than the next stretch's cost makes it go down, and a generous one makes it go up. - Return -1 if
totalis negative. The lap can't be paid for. Otherwise a start exists and the second loop finds it. - Declare
startas 0. Station 0 is tried first, and the candidate only moves when it fails. - Declare
tankas 0. The car starts empty. - Loop over the stations once more, from 0 to
n - 1. One drive from the beginning to the end of the list is enough. - Take station
i's gas and drive its stretch:tank += gas[i] - cost[i]. Afterwards the tank holds what is left on arriving at the next station. - Check whether
tankis negative. A tank of exactly 0 is fine: the car arrives empty and can take the next station's gas. - Move
starttoi + 1inside thatif. This is the key step: all stations up toiare ruled out. - Reset
tankto 0, because the trip now begins again at the new start. - Return
startafter the loop.
The solution in Go
func canCompleteCircuit(gas []int, cost []int) int {
n := len(gas)
total := 0
for i := 0; i < n; i++ {
total += gas[i] - cost[i]
}
if total < 0 {
return -1
}
start := 0
tank := 0
for i := 0; i < n; i++ {
tank += gas[i] - cost[i]
if tank < 0 {
start = i + 1
tank = 0
}
}
return start
}
The Go details worth a closer look:
- The compound assignment
+=.total += gas[i] - cost[i]adds the difference to the running value. The right-hand side is computed first, so it is the same astotal = total + (gas[i] - cost[i]). :=declares and infers.total := 0makes anint. Go refuses to compile if a declared variable is never used, so every variable here has a job.- Slices and
len.gasandcostare slices, and the function only reads them, so nothing is copied or changed.len(gas)is the number of stations, and the constraints saycosthas the same length. - No overflow. Go's
intis 64 bits. The sum is at most 100,000 × 10,000 in size, far from the limit. startcan't reachnwhentotalis non-negative. If the tank went negative at the last station, the earlier skipped stretches and this one would together sum to a negative total, which the first check already excluded. So the value returned is always a valid index.
Complexity
Time: O(n). There are two simple passes over the stations, and each does constant work per station.
Space: O(1). The function keeps only n, total, start, tank and the loop variable.
Edge cases and common mistakes
- Total gas less than total cost. The first check returns -1 immediately, as in
gas = [2, 3, 4],cost = [3, 4, 3]. - One station.
gas = [5],cost = [4]returns 0, andgas = [4],cost = [5]returns -1. When gas equals cost, as in[3]and[3], it returns 0: an empty tank on arrival is allowed. - Treating 0 as a failure. Writing
tank <= 0would reject a start that arrives at the next station with exactly nothing, which is valid. The check istank < 0. - Forgetting to reset the tank. If
tankkeeps its negative value after the candidate moves, the new start looks worse than it is. - Skipping the total check. Without it the second loop returns some station even when no start exists. For
gas = [4],cost = [5]the second loop alone would return 1, which isn't even a valid station.
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.gas = [1, 2],cost = [2, 1]gives1.
