What Is the Circular Gas Station Problem?
You have N gas stations arranged in a circle. Station i refuels you by gain[i], but driving to the next station costs cost[i]. The tank starts empty and has unlimited capacity.
The goal is to find a station to start from so you can visit every station exactly once clockwise and return to where you began. Return -1 if no such start exists.
On AlgoNote we framed this as a friendly "Midnight Snack Truck" story: a truck looping around a circular street of food stalls, looking for the right place to start.
The Key Is the Diff
Define diff[i] = gain[i] - cost[i] for each station and the problem simplifies:
- •
diff[i] > 0→ fuel grows as you pass that station - •
diff[i] < 0→ fuel shrinks
If the total sum is negative, no start can complete the loop, because total cost exceeds total refuel. So we check the total first.
Why Move the Start Forward?
The core greedy property:
If, accumulating from candidate start, the running sum first goes negative at station i, then no start between start and i can pass i either.
The proof is short. If the sum from start to i is negative, then the segment sum from a middle point j to i equals (start..i sum) − (start..j-1 sum). The start..j-1 part was non-negative (i is the first negative point), so the j..i sum ≤ start..i sum < 0. Starting at j gets stuck at i just the same.
So it is safe to jump the candidate straight to i+1 and reset the tank to 0. This jump is what gives us a single O(n) scan.
How It Works
Step 1. Initialize total = 0, tank = 0, start = 0.
Step 2. At each station i, add diff = gain[i] - cost[i] to both total and tank.
Step 3. If tank < 0, move start = i + 1 and reset tank = 0.
Step 4. After the scan, return start if total >= 0, otherwise -1.
Here "accumulating" and "moving the start" are two distinct actions. The AlgoNote visualization shows each of them as a separate step.
Time and Space Complexity
| Complexity | |
|---|---|
| Time | O(n) |
| Space | O(1) |
The naive approach of testing every start with a full loop is O(n²), but the greedy property above solves it in a single O(n) scan.
Walking Through an Example
For gain = [2, 4, 1, 6, 3], cost = [4, 1, 5, 2, 2], we get diff = [-2, +3, -4, +4, +1], total +2.
- •start=0: diff[0]=-2 → tank=-2 < 0 → move start=1
- •start=1: diff[1]=+3 → tank=3, diff[2]=-4 → tank=-1 < 0 → move start=3
- •start=3: diff[3]=+4 → tank=4, diff[4]=+1 → tank=5
The surviving start=3 is the answer.
Common Mistakes
- •Skipping the total check: returning start without verifying
total >= 0misses impossible cases. - •Reset timing: the moment tank goes negative, move start and reset tank to 0.
- •Overcomplicating the circle: this greedy needs no modular indexing — one linear scan is enough (the answer, if any, is unique).
See It in Action on AlgoNote
Watch how the diffs accumulate and how the start jumps when the tank dips below zero, step by step on AlgoNote.