Problem overview
There are n 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] units. 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 and then drive on.
canCompleteCircuit(_ gas: [Int], _ cost: [Int]) -> Int returns the index of the station to start from so that you can drive once around the circle and return to it, or -1 if no start works. At most one start works.
In the first example, gas = [1, 2, 3, 4, 5] and cost = [3, 4, 5, 1, 2], the answer is 3. The tank holds 4 at the start, then 8 at station 4, 7 at station 0, 6 at station 1 and 5 at station 2. Driving back to station 3 costs 5, which is exactly what is left. In the second example, gas = [2, 3, 4] and cost = [3, 4, 3], there are 9 units of gas for a trip that costs 10, so the answer is -1.
Approach: skip every start that fails
Trying each station as a start and simulating the lap costs O(n²), which is too slow for 100,000 stations. The greedy solution makes two observations and needs one pass for each.
Is the trip possible at all? Add up gas[i] - cost[i] over every station. If the total is negative, the lap costs more than all the gas there is, and no start works. Return -1.
Where does it start? Otherwise, drive once from station 0 to the last station while keeping the gas in the tank and a candidate start, which is 0 at first. Whenever the tank drops below 0 on the stretch after station i, the car couldn't have driven that stretch. Then move the candidate to i + 1 and empty the tank. At the end, the candidate is the answer.
Skipping is safe because of this. Starting at the old candidate, the car reached each station up to i with 0 or more gas. Starting at one of those stations instead means being there with an empty tank, which is never better, so the tank would still go below 0 after station i. None of them can be the start, and the next station to try is i + 1.
The last candidate works because the car reaches the end of the list from it without running dry. Each stretch skipped before it loses gas overall, but the total isn't negative, so the gas left at the end covers everything those stretches lost. That gas is enough to get through them and back to the start.
The second pass on the two examples:
gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]
i=0 tank=0 start=1 (dry)
i=1 tank=0 start=2 (dry)
i=2 tank=0 start=3 (dry)
i=3 tank=3 start=3
i=4 tank=6 start=3
gas = [5, 1, 2, 3, 4], cost = [4, 4, 1, 5, 1]
i=0 tank=1 start=0
i=1 tank=0 start=2 (dry)
i=2 tank=1 start=2
i=3 tank=0 start=4 (dry)
i=4 tank=3 start=4
Each line shows the tank and the candidate after station i, with the tank reset to 0 when it ran dry. Both runs end with the expected answers, 3 and 4.
Step by step
- Store the number of stations,
gas.count, in a constantnwithlet. - Declare
totalas avarset to 0. It sums what each station gives minus what the stretch after it costs. - Loop
iover0..<n, one pass over all the stations. - Add
gas[i] - cost[i]tototalinside the loop. - If
total < 0, return -1. The lap costs more than all the gas there is. Otherwise a start exists, and the second loop finds it. - Declare
startas avarset to 0. Station 0 is tried first, and the candidate moves forward only when it fails. - Declare
tankas avarset to 0, the gas in the tank when driving fromstart. - Loop
iover0..<nagain. One drive from station 0 to the last station is enough. - Add
gas[i] - cost[i]totank. Nowtankis the gas left on arriving at the next station. - Check
tank < 0. Exactly 0 is fine: the car arrives with an empty tank and can still take the next station's gas. - Inside the check, move
starttoi + 1, the station after the stretch where the tank ran dry. - Set
tankback to 0, because the trip now begins again at the new start. - After the loop, return
start.
The solution in Swift
class Solution {
func canCompleteCircuit(_ gas: [Int], _ cost: [Int]) -> Int {
let n = gas.count
var total = 0
for i in 0..<n {
total += gas[i] - cost[i]
}
if total < 0 {
return -1
}
var start = 0
var tank = 0
for i in 0..<n {
tank += gas[i] - cost[i]
if tank < 0 {
start = i + 1
tank = 0
}
}
return start
}
}
The Swift details worth a closer look:
0..<nis a half-open range. It covers 0 up ton - 1, which is exactly the valid indices. The lesson has at least one station, so the range is never empty, and0..<0would be a valid empty range anyway.letandvar.nnever changes, so it is alet.total,startandtankchange inside the loops, so they arevar. Swift reports a compile warning when avaris never changed, which is a useful hint.Intis 64 bits. With up to 100,000 stations and values up to 10,000, the sums reach about a billion in absolute value, far below the 64-bit limit. In Swift an overflowing addition stops the program rather than wrapping, but it can't happen here.startnever reachesn. It would only becomenif the tank ran dry at the last station, but then every skipped stretch, including the last one, would have a negative sum, and the total would be negative too. The total check has already returned -1 in that case.
Complexity
Time: O(n). Two simple passes over the stations, each with constant work per station.
Space: O(1). Only the integers n, total, start and tank are stored, whatever the input size.
Edge cases and common mistakes
- Total gas below total cost. The result is -1 straight away.
canCompleteCircuit([2, 3, 4], [3, 4, 3])returns -1. - One station.
canCompleteCircuit([5], [4])returns 0,canCompleteCircuit([4], [5])returns -1 andcanCompleteCircuit([3], [3])returns 0: arriving with exactly zero is allowed. - Using
tank <= 0as the failure test. A tank of exactly 0 is fine, because the car arrives with an empty tank and takes the next station's gas. Resetting there would move the start past a station that works. Only a negative tank means the stretch couldn't be driven. - Forgetting to reset
tank. The new start begins with an empty tank. Leftover negative gas from the old start would make later stretches look worse than they are. - Skipping the total check. Without it, the second loop still returns some station, even when no start works. For
[2, 3, 4]and[3, 4, 3]it would give a wrong index instead of -1. - Simulating the circle. A solution that tries every start and drives the whole lap is correct but takes
O(n²)time.
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.
