Problem overview
There are n stations on a circular road. Station i gives gas[i] units of gas, and driving from station i to the next 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, but only if the tank holds at least the cost of the stretch.
canCompleteCircuit(gas, cost) returns the station to start from so that you complete one full circle, 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. Starting there you take 4, drive to station 4 (cost 1) and take 5, which leaves 8, and the tank never drops below what the next stretch needs, ending with exactly 5 for the last stretch. 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: one pass with a moving start
The brute force tries each station as the start and simulates the whole circle, which takes O(n²) and is too slow for n up to 100,000. The note asks for O(n) time and O(1) extra space, which calls for a greedy idea built on two observations.
The total decides whether a start exists
Define the gain at station i as gas[i] - cost[i]: the gas you take there minus the cost of the stretch after it. If all the gains add up to a negative number, the trip costs more than all the gas there is, and no start can work. If the total is not negative, a start exists, and the only job left is to find it.
A failure rules out every station before it
Drive from station 0, tracking the gas in the tank, and keep a candidate start, first 0. When the tank drops below 0 after the stretch that follows station i, the car could not have made it from start. Moving the candidate to i + 1 and emptying the tank restarts the trip there.
Skipping all the stations from start to i is safe. From start, 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 drop below 0 after station i. None of them can be the answer.
The last candidate works because it reaches the end of the list without running dry, and the total isn't negative. Every stretch it skipped loses gas overall, but the gas the candidate has left at the end is at least what those stretches lose together. Inside a skipped stretch the tank only goes negative at its very end, so with that gas the car gets through each skipped stretch and back to the start.
On the third example, gas = [5, 1, 2, 3, 4] and cost = [4, 4, 1, 5, 1], the gains are 1, -3, 1, -2, 3. Their total is 0, so a start exists. Walking through them:
i=0 gain 1 tank 1 start 0
i=1 gain -3 tank -2 -> start 2, tank 0
i=2 gain 1 tank 1 start 2
i=3 gain -2 tank -1 -> start 4, tank 0
i=4 gain 3 tank 3 start 4
The answer is 4.
Step by step
- Store
n = len(gas). The route is a circle, so after stationn - 1comes station 0. - Start
totalat 0. It adds up the gas taken minus the gas spent over all the stations. - Loop
ioverrange(n). One pass over the stations. - Add
gas[i] - cost[i]tototal. A station whose gas is less than its stretch costs makes a negative contribution, a richer one a positive contribution. - If
total < 0, return -1. All the gas can't pay for the trip, so no start works. Otherwise a start exists. - Set
start = 0. Station 0 is tried first, and the start moves only when it fails. - Set
tank = 0. The car begins with an empty tank. - Loop
ioverrange(n)again. A single drive from station 0 to the last station is enough. - Add
gas[i] - cost[i]totank. Afterwardstankis the gas left on arriving at the next station. - If
tank < 0, the car couldn't drive this stretch fromstart. A tank of exactly 0 is fine: the car arrives empty and takes the next station's gas. - Move
starttoi + 1. This is the key step. No station from the old start toican be the start either. - Reset
tankto 0. The trip begins again at the new start with an empty tank. - Return
start. The total check showed a start exists, and none of the skipped stations can be it.
The solution in Python
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
n = len(gas)
total = 0
for i in range(n):
total += gas[i] - cost[i]
if total < 0:
return -1
start = 0
tank = 0
for i in range(n):
tank += gas[i] - cost[i]
if tank < 0:
start = i + 1
tank = 0
return start
Python details to keep in mind:
- Two separate loops. The first computes
totaland the second movesstart. They use the same expression,gas[i] - cost[i], but they answer different questions, so they keep separate variables. startcan reachninside the loop. If the tank goes negative at the last station,startbecomesn. That can't happen when the code reaches the finalreturn, because a non-negative total means the last candidate always makes it to the end of the list.- No wrap-around indexing. Despite the circular route, the code never uses
%or a second lap. The total check replaces the second lap. - Plain integers. Python integers don't overflow, so sums of up to 100,000 values of up to 10,000 need no care.
Complexity
Two passes over the stations, each doing constant work per station, take O(n) time. The code keeps only n, total, start, tank and the loop variable, so the extra space is O(1).
Edge cases and common mistakes
- One station.
canCompleteCircuit([5], [4])is 0 andcanCompleteCircuit([4], [5])is -1. - Exactly enough gas. When the total is exactly 0, a start can still work, as in the first example. Test
total < 0, nottotal <= 0. For the same reason, a tank of exactly 0 must not trigger a restart. - Everything balanced. With
gas = [3, 3]andcost = [3, 3]every stretch is just affordable from the first station, and the answer is 0. - Forgetting to reset the tank. Moving
startwithout settingtankto 0 carries debt from the old start into the new one. - Returning early. Moving
starttoi + 1is a guess that only the rest of the pass can confirm. The loop must run to the end of the list. - Skipping the total check. Without it, the code would return a candidate even when no start works.
Testing
canCompleteCircuit([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]) -> 3
canCompleteCircuit([2, 3, 4], [3, 4, 3]) -> -1
canCompleteCircuit([5, 1, 2, 3, 4], [4, 4, 1, 5, 1]) -> 4
canCompleteCircuit([5], [4]) -> 0
canCompleteCircuit([4], [5]) -> -1
canCompleteCircuit([3, 3], [3, 3]) -> 0
