Circular routes (gas station)
In one line
If total gas covers total cost a valid start exists, and it is the station right after the last point where the running tank went negative.
What it is
The gas station problem: n stations sit on a circular road. Station i gives gas[i] fuel and driving to the next station costs cost[i]. Starting with an empty tank, find a station from which you can drive all the way round once, or return -1. If a solution exists it is guaranteed unique in the classic version.
Trying every start and simulating is O(n^2). The greedy solution is one pass in O(n) based on two facts. First, a full loop is possible from some start if and only if the total of gas[i] - cost[i] is at least 0. Second, if you start at s and first run out before reaching station j + 1, then no station between s and j can be the start either.
The second fact lets you skip whole blocks of candidates at once: when the tank goes negative at i, jump the candidate start to i + 1 and reset the tank.
Why interviewers ask
This is a favourite because the O(n^2) simulation is obvious but the O(n) solution requires a short proof. Interviewers want to hear why resetting the start past the failure point is safe and why total >= 0 guarantees success, not just the code.
How it works
- 1Compute diff[i] = gas[i] - cost[i], the net fuel change from station i to i + 1.
- 2Keep total (sum of all diffs), tank (sum since the current candidate start) and start = 0.
- 3For each i: add diff[i] to both total and tank. If tank < 0, the trip from start cannot reach i + 1, so set start = i + 1 and tank = 0.
- 4Why skipping is safe: for any k between start and i, you arrived at k from start with tank >= 0. Starting fresh at k gives you less or equal fuel at every later point, so k also fails by i + 1.
- 5At the end, if total < 0 no start works (you need more fuel than exists). Otherwise start is the answer: the segment from start to the end never went negative, and the deficit of the earlier part is covered because total >= 0.
Worked example · gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]
- diff = [-2, -2, -2, 3, 3]. total will be -2 - 2 - 2 + 3 + 3 = 0, which is >= 0, so an answer exists.
- i=0: tank = -2 < 0. Station 0 cannot reach station 1. start = 1, tank = 0.
- i=1: tank = -2 < 0. start = 2, tank = 0.
- i=2: tank = -2 < 0. start = 3, tank = 0.
- i=3: tank = 3. i=4: tank = 6. The loop ends with start = 3.
- Check by hand from station 3: fill 4, drive cost 1, tank 3; fill 5 (8), cost 2, tank 6; fill 1 (7), cost 3, tank 4; fill 2 (6), cost 4, tank 2; fill 3 (5), cost 5, tank 0 back at station 3. It works with exactly 0 left.
Picture it
Think of a monthly budget where some months you earn more than you spend and some months less. If the year as a whole breaks even, there is a month to start the year from so your balance is never negative: start right after the month where your running balance hit its lowest point.
Reference code
def can_complete_circuit(gas, cost):
"""Return the unique start station index, or -1 if impossible."""
total = 0 # net fuel over the whole loop
tank = 0 # net fuel since the current candidate start
start = 0
for i in range(len(gas)):
diff = gas[i] - cost[i]
total += diff
tank += diff
if tank < 0: # cannot reach i + 1 from `start`
start = i + 1 # nothing in start..i works either
tank = 0
return start if total >= 0 else -1
# can_complete_circuit([1,2,3,4,5], [3,4,5,1,2]) -> 3
# can_complete_circuit([2,3,4], [3,4,3]) -> -1
One pass keeps the overall balance and the balance since the current candidate. Whenever the candidate fails, every station up to the failure point is ruled out at once. O(n) time and O(1) space.
Key patterns
Net balance + reset
When: Find a start on a circle where a running sum never goes negative
How: Reset the candidate start to i + 1 whenever the running sum drops below 0; check total >= 0.
Start after the minimum prefix
When: Same problem, viewed through prefix sums
How: The valid start is the index after the position where the prefix sum of diffs is smallest.
Doubling the array
When: Circular problems that need a simulation or a sliding window
How: Conceptually iterate i from 0 to 2n - 1 using i % n, so a window can wrap around.
Feasibility from totals
When: Any loop or cycle with supply and demand
How: First check the global sum; if supply < demand no local trick helps.
Real-world use
Electric vehicle and delivery loop planning
Fleet tools for fixed circular routes (campus shuttles, mail rounds, EV delivery loops with chargers) check whether a vehicle can complete the loop and from which depot to start using exactly this net-energy sweep.
Cash flow planning
Finance teams look for the point to start a recurring cycle (a fiscal period, a billing cycle) so the running balance never dips below zero; it is the index after the minimum prefix sum.
Circular buffers and round-robin systems
When work arrives and is consumed around a ring, such as tokens in a token bucket or credits in round-robin schedulers, finding a starting slot where credit never goes negative uses the same prefix-sum reasoning.
Mountain and pipeline logistics
Any closed tour with supply points and consumption between them, such as water stations on a looped hiking trail or pumping stations on a ring main, reduces to this problem.
In a project
A city runs an electric shuttle on a fixed loop of 12 stops; some stops have chargers that add a set amount of charge during a dwell, and each segment uses a known amount. The operator wants to know where the shuttle should start its day and whether a battery downgrade is safe.
- For each stop, compute charge added minus energy used on the next segment, in kWh.
- Run the one-pass sweep to get the total and the valid starting stop; if the total is negative, report the shortfall.
- Also track the minimum tank level along the loop from the chosen start, which is the minimum battery buffer the shuttle needs.
- Rerun the check with each proposed battery size and seasonal consumption figures (winter heating) to see which configurations still work.
Impact: The operator gets a clear start stop and a safety margin per season in milliseconds, instead of trial runs, and can show exactly how much charge a smaller battery would leave in winter.
Trade-offs
Use it when
- A circular route with a gain and a cost per step
- You need a valid starting point where a running total stays non-negative
- Input is large and O(n^2) simulation is too slow
Avoid it when
- You can refuel only partially or the tank has a capacity limit (the problem changes and may need a heap or DP)
- The route is not fixed (that is a shortest path or routing problem)
- You need all valid starts in a version without uniqueness (check each start with prefix sums instead)
Cost: O(n) time and O(1) space, versus O(n^2) for trying every start.
Common mistakes
- Simulating from every start in O(n^2).
- Forgetting the total >= 0 check and returning a start that does not actually work.
- Moving start to i instead of i + 1 after a failure at i.
- Not being able to explain why stations between the old start and the failure point are skipped safely.
- Assuming a tank capacity limit that the problem does not have.
Interview questions
Quick revision
- diff[i] = gas[i] - cost[i].
- total < 0 means impossible: return -1.
- tank < 0 at i: start = i + 1, tank = 0.
- Stations between a failed start and the failure point also fail.
- Answer = index after the minimum prefix sum.
- O(n) time, O(1) space.
- Classic version guarantees a unique answer.
Check yourself
1. gas = [1,2,3,4,5], cost = [3,4,5,1,2]. Which start works?
2. If sum(gas) < sum(cost), what is true?
3. Running from start s, the tank first goes negative at station i. Where does the next candidate start?
4. What is the time complexity of the greedy solution?
Saved on this device. Create a free account to keep it on every device.
Practise this with Sam
A real mock interview, out loud, with an honest scorecard. Free to start.