The problem
Gas stations sit on a circular road. At station i you can fill up gas[i], and driving to the next station costs cost[i]. Starting with an empty tank, from which station can you drive the whole loop? Return −1 if none.
Input: gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2] Output: 3
Picture it
Picture a road trip around a ring of petrol stations. If the total fuel is less than the total cost, no start works. Otherwise drive from station 0 keeping a tank balance. If the tank ever goes negative, none of the stations from the current start up to here could be a valid start, so we restart the trip at the next station with an empty tank.
How to recognise it
- Stations sit on a circle, and you must pick a starting point such that a running balance never goes below zero for a whole lap.
- Each station contributes a net amount,
gas[i] - cost[i], so the problem is about prefix sums of those amounts. - Up to 10^5 stations: trying each start with a full lap is O(n²), about 10^10 steps.
- When one failure at position i rules out many starts at once, a greedy single pass is possible.
Start with brute force
Try every station as the start and simulate a lap, stopping as soon as the tank goes negative.
def circuit_brute(gas, cost):
n = len(gas)
for s in range(n):
tank = 0; ok = True
for k in range(n):
i = (s + k) % n
tank += gas[i] - cost[i]
if tank < 0:
ok = False; break
if ok:
return s
return -1
Each start can need up to n steps, so time is O(n²): about 10^10 for n = 10^5, too slow. Space is O(1).
From brute force to the idea
- Total check first. If the total gas is less than the total cost, no start works, so return −1. If it is at least the total cost, some start does (this is the part that needs a short argument, given below).
- Run one lap from station 0, keeping a
tankof net gas. If the tank falls below 0 at station i, you could not get past i from the current start. - Rule out every start in between. The run from
starthad a tank of at least 0 at every station before i. A start at a later station k would arrive at each station up to i with a tank no bigger than that (it lacks the leftover from before k). So none of them can get past i either. - Restart after the failure. Set
start = i + 1andtank = 0. - Why the last start works. The total is non-negative, and all earlier failures were "debts" before
start. The stretch fromstartto the end has a non-negative balance in every prefix (a negative prefix would have movedstartagain), and what is left is enough to cover the debts at the beginning of the circle.
This is the key idea: when the tank goes negative at i, no start up to i can work, so jump to i + 1; the total check guarantees the final candidate completes the lap.
The key idea
One pass: reset the start to i + 1 whenever the running tank drops below 0. O(n).
Python solution
def can_complete_circuit(gas, cost):
if sum(gas) < sum(cost):
return -1 # not enough fuel in total
tank, start = 0, 0
for i in range(len(gas)):
tank += gas[i] - cost[i]
if tank < 0: # ran dry: no start up to i works
start, tank = i + 1, 0
return startIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n²): up to n steps from each of n starts | O(1): a tank value |
| Greedy (shown code) | O(n): sum twice plus one loop, each linear | O(1): tank and start |
Edge cases
- One station (
[5], cost[4]): returns0; with[1]and[1]it also returns0since the tank stays at 0. - Not enough total (
[2, 3, 4]with cost[3, 4, 3]): returns-1. - Standard example (
[1, 2, 3, 4, 5]with cost[3, 4, 5, 1, 2]): returns3. - Ties (
[3, 3]with cost[3, 3]): returns0; both stations work here, and the problem guarantees the answer is unique, so this input does not occur. - Zero tank is fine: the code only restarts when the tank is strictly below 0, so arriving with exactly 0 is allowed.
- Large values: Python integers do not overflow; in other languages sums of 10^5 values up to 10^4 stay within 32-bit range (10^9).
Common mistakes
- Skipping the
sum(gas) < sum(cost)check: for[2, 3, 4]with cost[3, 4, 3]the loop ends withstart = 2and returns 2 instead of −1. - Restarting at
iinstead ofi + 1, which retries the very station that caused the failure. - Not resetting
tankto 0 when restarting. - Simulating a full lap from the final
startto verify it. The total check makes that unnecessary.
You must start at station 0, but the tank may begin with some fuel. Find the smallest starting fuel that lets you drive the whole lap, or -1 if the total gas is less than the total cost. For gas [1, 2, 3, 4, 5] and cost [3, 4, 5, 1, 2] the answer is 6. Describe your approach, then write it if you like.
Compare with our answer
The tank after each station is the starting fuel plus the running total of gas - cost. It must never go below 0, so the starting fuel is the negative of the lowest running total (or 0 if that is never negative).
def min_start_fuel(gas, cost):
if sum(gas) < sum(cost):
return -1
tank = worst = 0
for g, c in zip(gas, cost):
tank += g - c
worst = min(worst, tank)
return -worst
min_start_fuel([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]) is 6 and min_start_fuel([2, 3, 4], [3, 4, 3]) is -1. Time O(n), space O(1).
A strong answer mentions: prefix sums of net gas, the lowest prefix sum being the biggest deficit, starting worst at 0 so the answer is never negative, and the total check for the -1 case.
1. A circular delivery route has n depots with net fuel gains and losses (some negative). You must find a depot to start from, with an empty tank, so the tank never goes negative on one lap. n is up to 100,000. Which approach fits best?
When the tank fails at depot i, no start up to i can work, so the scan restarts at i + 1; one pass is enough. The all-starts simulation is O(n²) (10^10 steps), and the largest-gain and sorting heuristics can be fooled by a later large loss.
2. The code restarts start after every failure. Why is it still O(n) and not O(n²)?
Restarting just moves start and zeroes tank; the loop variable i keeps going, so there are n iterations in total. The brute force is the one that re-simulates laps. Restarts can occur many times (even at every station), and the sum check runs once before the loop.
3. A learner deletes the if sum(gas) < sum(cost): return -1 line. For which input does the function now return a wrong answer?
Only the last input has too little total gas, so without the check the loop wrongly returns station 2 instead of −1. The other three inputs are solvable and the loop alone finds the right start (3, 0 and 0).
Score 60% or more and the lesson is marked complete.