Minimum Number of Refueling Stops

Minimum Number of Refueling Stops is a classic greedy + heap problem. It teaches a beautiful trick: make decisions as late as possible. Instead of deciding to refuel the moment you pass a station, you remember every station you pass and only "spend" one when you are actually stuck — and then you spend the best one available.

The slow way first

You could try every subset of stations and check which combinations reach the target with the fewest stops — but that is exponential. A smarter brute force is dynamic programming over dp[k] = the farthest you can reach using k stops, which is O(n²). It works, but for large inputs it is slow, and it hides the simple intuition.

The question to ask: when I am forced to refuel, which station should I have stopped at? The answer is obvious in hindsight — the one with the most fuel among the stations I have already driven past.

The idea: bank every station, spend the biggest when stuck

Drive forward greedily. Every station you can reach, you do not refuel at — you just drop its fuel into a max-heap as a future option. When your range can no longer reach the next station (or the target), you are stuck: pop the largest fuel from the heap, count it as one stop, and add it to your range. Repeat until you reach the target or the heap is empty (impossible).

The key insight: deferring the choice lets us always make the optimal refuel decision, because by the time we are stuck we have seen every station that was ever reachable for free.

Walk through it

Step through the animation. The range pointer marks how far we can drive. As we pass each station, its fuel joins the heap label. At position 20 we stall — pop the biggest (60), one stop, range jumps to 70. We coast past the rest, then stall again before the target — pop 40, second stop, range hits 110. Done in 2 stops.

Pseudocode

heap = empty max-heap, fuel = start, stops = 0, i = 0
while fuel < target:
    while next station's position <= fuel:        # every reachable station
        push its fuel onto the max-heap
        advance i
    if heap is empty:
        return -1                                 # stuck, cannot reach target
    fuel += pop the largest fuel from the heap    # spend the best option
    stops += 1
return stops

The Python solution

def min_refuel(target, start, stations):
    heap, fuel, stops, i = [], start, 0, 0
    while fuel < target:
        while i < len(stations) and stations[i][0] <= fuel:
            heappush(heap, -stations[i][1])
            i += 1
        if not heap:
            return -1
        fuel += -heappop(heap)
        stops += 1
    return stops

• heap is a max-heap of fuel from stations we have already passed. Python only has a min-heap, so we push negatives (-stations[i][1]) and negate again on pop.
• The outer while fuel < target loops until our range covers the target.
• The inner while banks every station whose position is within our current range, pushing its fuel and advancing i.
• if not heap: return -1 means we are stuck with no banked station — the target is unreachable.
• Lines 9–10 are the greedy move: pop the largest fuel, extend our range, and count one stop.

Complexity

Each station is pushed and popped from the heap at most once, and heap operations are O(log n), giving O(n log n). The heap holds at most every station, so the extra space is O(n).

When this pattern shows up

Practice