Making a DP Faster & the Refuel Plan
In short: a DP transition that scans a sliding window for a minimum
(cost[i] = fees[i] + min(cost[i − reach..i − 1])) does the same comparisons
over and over, because consecutive windows mostly overlap. A monotonic
deque fixes it by keeping only candidates that could still win: anything
older and no cheaper than a newer arrival can never be the answer again,
so it's evicted for good. What's left increases front to back, the cheapest
always at the front, and every station is pushed once and popped at most
once — O(1) amortised per station instead of O(reach).
Meridian's long-haul van crosses the region on a road lined with fuel stations.
Each one charges a different stop fee, and the tank only reaches so far, so
consecutive stops can be at most reach stations apart. The van has to stop at
the first station and the last. Which stations should it use?
You already know how to write this DP:
cost[i] = fees[i] + min(cost[i − reach], …, cost[i − 1])
It's correct, and it scans up to reach cells for every station. On a
route with 200,000 stations and a reach of 500 that's 100 million reads for
one plan, and dispatch wants to re-plan every time a price changes. This
lesson doesn't find a new DP. It takes a DP you already have and makes the
inner loop disappear.
Where the time goes
Count the reads the scan makes on a short route:
reads = 0
n, reach = 10, 3
for i in range(1, n):
for j in range(max(0, i - reach), i):
reads += 1
print(reads)Look at what consecutive stations actually scan. Station 5 looks at 2, 3, 4.
Station 6 looks at 3, 4, 5. The window slides forward by one: one station
leaves at the back, one arrives at the front, and the other reach − 1 are
the same stations as last time. The scan throws away everything it learned and
starts again, every time.
Keeping only the stations that could still win
Suppose station 5 costs 9 and station 4 costs 13. Station 4 is older, so it will fall out of reach sooner, and it's dearer. No future station will ever prefer it to station 5. It can be forgotten for good.
Do that every time a station arrives, and what's left is a queue of stations whose costs increase from front to back, with the cheapest at the front:
- Expire: drop the front while it's out of reach (
< i − reach). - Read: the front is the cheapest station in reach, so
cost[i] = cost[front] + fees[i]. - Evict: pop the back while its cost is
>=cost[i], since those are older and no cheaper. - Join: append
iat the back.
A queue you can pop from both ends is a collections.deque. Here's the
refuel plan on eight stations with a reach of 3, with the deque's stations
highlighted:
Each station reads one cell, the front of the deque, instead of scanning its whole reach. The highlighted cells are the deque, and their costs always increase from front to back.
Station 0 is the start, so its cost is its own fee, 4. The deque holds [0]. 8 cells. At index 0.
That last caption is the whole complexity argument. Each station is appended
once and popped at most once, from one end or the other, so all the
while loops together do at most n pops over the whole route. The run costs
O(n) time, amortised, no matter how big reach is — nothing about the
cost per station's turn in the deque grows with reach, only the total
pushes and pops across the whole run do. The deque holds O(n) space in
the worst case, same as the cost array it's built from, but usually far
fewer: it only keeps the stations still cheap enough to matter.
The eviction rule is easy to get backwards, so predict what survives:
from collections import deque
vals = [5, 3, 4, 1, 2]
dq = deque()
for i, v in enumerate(vals):
while dq and vals[dq[-1]] >= v:
dq.pop()
dq.append(i)
print(list(dq))Forgetting step 1 is the classic bug, because the deque then remembers a station the tank can't actually reach:
The cheapest legal plan is 0, 2, 4 for 1 + 50 + 5 = 56, but this prints 6: it jumps straight from station 0 to station 4. Drop stations from the front once they're out of reach.
Now run the deque yourself. Every frame shows the stations in reach (the window), the deque's stations and its front. Change the fees or the reach and run it again:
Your deque at work. The highlighted window is what a scan would read, and the candidates are all the deque keeps.
Watch the deque itself, one index at a time, on a smaller example:
Measured, not claimed
Scale that up to a route of 200,000 stations and a scan that manages 10 million reads a second. The scanning DP reads about 200,000 × reach cells, so it takes 0.1 s at a reach of 5, a full second at 50 and 10 seconds at 500. The deque makes fewer than 600,000 moves whatever the reach, under 0.06 s. The DP is the same in both. What changed is how the minimum over the window is found.
The pattern, stated once
The deque works because of two properties of the transition, and it's worth checking both before reaching for it:
- The candidates form a window that only slides forward. As
igrows, both the oldest allowedjand the newest move forward, so a candidate that falls out never comes back. - What you're minimising depends on
jalone.cost[j]ranks the candidates the same way for everyi, andfees[i]is added afterwards. So "older and no better" means "never better", and that's what allows the pop.
Swap min for max and the deque keeps values decreasing instead. Swap it for
a sum and you don't need a deque at all: add the newcomer and subtract the
one that falls out, as the drill exercise does when counting plans. Here's an
interview-style problem that needs one extra step before it fits the shape:
Interview-style problem: the best chain. A driver picks a non-empty set of delivery slots from
values(some are negative). Consecutive picked slots must be at mostgapapart, but the chain may start and end anywhere. Return the highest total.Constraints: up to 100,000 slots,
1 ≤ gap ≤ n. O(n · gap) is too slow.Examples:
[3, -8, 2, -1, 5]with gap 2 →10(3, 2, 5).[-4, -2, -7]with gap 1 →-2.
The extra step is max(0, …): a chain either extends the best chain in the
window or starts fresh, whichever is larger. That's the boss exercise.
❓ Cross-question: "Couldn't a heap give me the window's minimum?" Yes, in O(log n) per station with lazy deletion of expired entries, which is O(n log n) overall. The deque is O(1) amortised, because it throws away candidates that can never win and a heap keeps them all.
| Transition shape | Tool | Per station |
|---|---|---|
min or max over a sliding window of f(j) |
monotonic deque | O(1) amortised |
| sum over a sliding window | running sum | O(1) |
min over all earlier j of f(j) |
one running minimum | O(1) |
| min over a window, with lazy expiry | heap | O(log n) |
f(j) + a(j) · b(i) (a term in i times a term in j) |
convex hull trick | O(1) to O(log n) |
Idioms & real-world patterns
Store indices, not values
The deque holds station numbers. The value is one lookup away, and the index is what you need to tell whether the front has fallen out of reach. A deque of values can't answer "is this still in reach?".
⚡ Advanced: when j and i multiply
If the cost is something like cost[j] + (i − j)², expanding it gives a term
−2 · i · j that mixes i with j. Now which candidate is best changes with
i, so the deque's fixed ordering breaks. Each candidate j is then a
line in b(i), and the answer is the lowest line at that point. Keeping
only the lines that are ever lowest (the lower envelope) is called the convex
hull trick. It's the same idea as the deque, discarding candidates that can
never win, applied to geometry instead of order.
Quick practice
from collections import deque
vals = [6, 2, 8, 3, 5]
dq = deque()
for i, v in enumerate(vals):
while dq and vals[dq[-1]] >= v:
dq.pop()
dq.append(i)
print(list(dq))The cheapest plan costs 14, but this prints 22 because nothing ever leaves from the back. Dearer, older stations pile up and get read by mistake. Add the eviction step back.
🎯 Your turn
Write cheapest_refuels(fees, reach). Stop at station 0 and at station
n − 1, never more than reach stations apart, paying the least in total. Return
{"fee": total, "stops": [station numbers in order]} in O(n).
cheapest_refuels([4, 7, 3, 8, 6, 2, 9, 5], 3)→{"fee": 14, "stops": [0, 2, 5, 7]}
Ties: each station's plan comes from the latest of the cheapest stations
in reach, which is what a deque that pops the back on >= gives you.
Then press ▶ Run, tap the Live App try chips, and hit ✓ Check. Green means the refuel plan is built. ✅