Gas Station
Find the unique starting station for a circular route using a total check and a running tank
Problem Statement
There are n gas stations arranged in a circle. Station i has gas[i] fuel, and driving from station i to i + 1 costs cost[i] fuel.
You start with an empty tank at some station. Return the index of the station from which you can complete the full circuit, or -1 if it is impossible. The answer is guaranteed unique if it exists.
Input: gas = [1, 2, 3, 4, 5]
cost = [3, 4, 5, 1, 2]
Output: 3
Input: gas = [2, 3, 4]
cost = [3, 4, 3]
Output: -1Intuition
Trying every start and simulating the loop is O(n²). Two observations collapse it to a single pass.
Observation 1 — is a solution even possible?
At each station you gain gas[i] - cost[i]. Over a full circle, the net change is sum(gas) - sum(cost).
Feasibility is a one-line check
If sum(gas) < sum(cost), the circuit consumes more fuel than exists anywhere on it. No starting point can work — return -1.
If sum(gas) >= sum(cost), a valid start is guaranteed to exist. So the only remaining job is to find it.
Observation 2 — failing tells you a lot
Suppose you start at station s and run out of fuel arriving at station f. What can you conclude?
The key insight
Every station between s and f is also a dead end.
Consider starting at some k strictly between them. Getting to k from s you had a tank of at least zero, so starting fresh at k gives you no more fuel than you had passing through it. If the richer version of the journey failed before f, the poorer one fails no later.
So the next candidate is f + 1. Skip the entire failed stretch — that is what turns O(n²) into O(n).
Real-world analogy
Planning a road trip on a ring road. First, check whether the total fuel available around the loop covers the total distance — if not, no starting town helps. If it does, drive and keep an eye on the tank. The moment you strand yourself, you know every town you passed through is equally bad, so restart the plan from the town after the breakdown.
Watch it run
Approach
Track three values in one pass
total — the running sum of gas[i] - cost[i] over the whole array, used for the feasibility check.
tank — the fuel since the current candidate start.
start — the current candidate.
If tank goes negative, reset
Set start = i + 1 and tank = 0. Everything from the old start through i is eliminated.
After the loop, return start if total >= 0, else -1
total is what proves a solution exists at all.
Solution
def can_complete_circuit(gas: list[int], cost: list[int]) -> int:
"""Index of the only valid starting station, or -1."""
total = 0 # net fuel over the entire circuit
tank = 0 # fuel accumulated since `start`
start = 0
for i in range(len(gas)):
diff = gas[i] - cost[i]
total += diff
tank += diff
if tank < 0:
# Stranded — every station from `start` to i is disqualified.
start = i + 1
tank = 0
return start if total >= 0 else -1Why the final `start` is guaranteed correct
Two facts combine:
- Every station before
startwas eliminated by the skipping argument. - From
startto the end of the array the tank never went negative — otherwisestartwould have moved again.
The wrap-around portion (from index 0 back to start) has net fuel total - tank, and since total >= 0 while tank >= 0, that stretch cannot strand you either. So start completes the circle. The problem's uniqueness guarantee means there is nothing else to check.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)
- Time — one pass. The brute force tries all
nstarts and simulates up tonsteps each, givingO(n²). - Space — three integers.
Edge Cases
Related Problems
- Jump Game — another greedy proof about which positions can be safely discarded
- Best Time to Buy and Sell Stock — a running value reset by a condition
- Candy — greedy applied in two directions