Minimum Number of Refueling Stops: Greedy with a Max Heap

A car starts at position 0 with startFuel liters of fuel. It needs to reach a target miles away. Along the way there are gas stations, each described by [position, fuel]. At each station, the car can refuel by the given amount (the tank has infinite capacity). Return the minimum number of refueling stops needed to reach the target, or -1 if it is impossible.

This is LeetCode 871: Minimum Number of Refueling Stops, a hard problem that rewards lazy decision-making. The trick is to never refuel until you absolutely must, and when you do, always pick the station that gives you the most fuel. A max heap makes this strategy efficient.

Why this problem matters

This problem teaches a powerful greedy pattern: defer a choice until you are forced to make it, then pick the best available option. You will see this "lazy greedy" approach in scheduling problems, resource allocation, and anywhere you need to minimize the number of interventions.

It also combines two fundamental ideas. First, the greedy decision rule (always take the biggest fuel available). Second, the max heap data structure that makes "find the biggest" an O(log n) operation instead of a linear scan. If you understand this problem well, you are prepared for a whole family of similar "minimize stops / moves / operations" questions.

The brute force and DP approaches

The most direct approach is DP. Let dp[i] be the farthest position reachable with exactly i refueling stops. Start with dp[0] = startFuel. For each station, update in reverse: if dp[i] can reach the station's position, then dp[i + 1] = max(dp[i + 1], dp[i] + fuel). Return the smallest i where dp[i] reaches the target.

def min_refuel_dp(target, startFuel, stations):
    n = len(stations)
    dp = [startFuel] + [0] * n
    for i, (pos, fuel) in enumerate(stations):
        for j in range(i, -1, -1):
            if dp[j] >= pos:
                dp[j + 1] = max(dp[j + 1], dp[j] + fuel)
    for i in range(n + 1):
        if dp[i] >= target:
            return i
    return -1

This runs in O(n^2) time and O(n) space. It works, but for up to 500 stations the quadratic cost is acceptable yet not ideal. More importantly, the DP approach does not reveal the intuition behind the problem. The greedy approach is both faster (O(n log n)) and more insightful.

The key insight: lazy refueling with a max heap

Imagine you are driving and you pass a gas station. You do not stop. Instead, you write down how much fuel that station had. You keep driving until your tank hits empty. Only then do you look at your notes and say, "I wish I had stopped at the station with the most fuel." You retroactively refuel from that station.

This is the core idea. You never commit to a stop until you are forced to. And when forced, you always pick the station that gives you the most fuel. This minimizes the total number of stops because each stop adds the maximum possible range extension.

A max heap stores the fuel values of all stations you have passed. When you run dry:

1. Pop the largest fuel value from the heap.
2. Add it to your tank.
3. Increment your stop count.
4. Keep driving.

If the heap is empty and you still cannot reach the next station (or the target), return -1.

Walking through it step by step

Let's trace through target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]. Green stations have been refueled at. Orange stations have been passed but not used.

The algorithm makes exactly 2 stops (at positions 10 and 60). Notice how it never decides to stop until it has to. It passes station 1 and station 2 without using them, because the fuel from station 0 was enough to keep going. When it runs out again at position 70, it retroactively refuels from station 3 (the best remaining option).

The greedy solution

import heapq

def minRefuelStops(target, startFuel, stations):
    heap = []
    fuel = startFuel
    stops = 0
    prev = 0

    for pos, cap in stations + [[target, 0]]:
        fuel -= (pos - prev)
        while fuel < 0 and heap:
            fuel += -heapq.heappop(heap)
            stops += 1
        if fuel < 0:
            return -1
        heapq.heappush(heap, -cap)
        prev = pos

    return stops

Here is what each piece does:

1. fuel -= (pos - prev): subtract the distance traveled since the last station. This tells you how much fuel you have left when you arrive at the current station.
2. while fuel < 0 and heap: if you ran out of fuel before reaching this station, retroactively refuel by popping the largest fuel value from the heap. Each pop counts as one stop.
3. if fuel < 0: return -1: if the heap is empty and fuel is still negative, you cannot reach this station no matter what. Return -1.
4. heapq.heappush(heap, -cap): add the current station's fuel to the heap (negated because Python's heapq is a min-heap, so negating gives max-heap behavior).
5. stations + [[target, 0]]: append the target as a dummy station with 0 fuel. This ensures the loop checks whether you can reach the target.

Complexity analysis

This is better than the O(n^2) DP approach. The log factor comes from the heap operations, and in practice the constant factors are small.

Building blocks

This problem is built on reusable patterns that CodeBricks drills independently.

1. Lazy greedy with a max heap

The pattern of collecting options as you go, then choosing the best one only when forced:

heap = []
for event in events:
    consume_resource(event)
    while resource < 0 and heap:
        resource += pop_best(heap)
        count += 1
    add_option(heap, event)

You see this whenever the problem asks for the minimum number of interventions. The key is that deferring a choice never makes things worse, because you always have at least as many options available later as you had earlier. Combined with always picking the best option, this guarantees optimality.

2. Simulating forward progress with a running variable

The pattern of tracking a position or resource level as you scan through sorted events. Here, fuel decreases by the distance between consecutive stations. This running-variable approach is simpler than maintaining absolute coordinates and recalculating from scratch at each step.

3. Max heap via negated min-heap

In languages without a built-in max-heap (like Python), you negate values to turn a min-heap into a max-heap. This is a small but critical implementation detail that shows up in many heap problems.

Edge cases

Before submitting, make sure your solution handles these:

• No stations at all stations = []: if startFuel >= target, return 0. Otherwise return -1. The loop only processes the dummy target station.
• Start fuel already reaches the target: return 0 immediately. The loop subtracts the full distance and fuel stays non-negative.
• Every station is needed: the answer equals len(stations). Each station's fuel gets popped exactly once.
• Impossible to reach: when the total available fuel (start + all stations) is less than the target. The algorithm returns -1 because the heap empties before fuel becomes non-negative.
• Stations at position 0: a station at position 0 costs nothing to reach. Its fuel gets added to the heap immediately.

The greedy approach handles all of these without special-case logic.

Common mistakes

1. Forgetting to process the target. If you only loop over stations and do not check whether the final fuel is enough to reach the target, you will miss cases where the car runs out between the last station and the target. Appending [target, 0] to the stations list is the cleanest fix.

2. Using a min-heap instead of a max-heap. Popping the smallest fuel value defeats the greedy strategy. In Python, remember to negate values when pushing and negate again when popping.

3. Not sorting stations. The problem states stations are sorted by position, but if you ever need to handle unsorted input, sort first. The greedy approach depends on processing stations in order of increasing position.

4. Stopping too early. Some people return stops as soon as fuel becomes non-negative inside the while loop. But you need to keep going to check all remaining stations and the target. Only return after the full loop completes.

From understanding to recall

The greedy heap solution is clean: one loop, one heap, one running fuel variable. Conceptually it makes perfect sense. You defer every decision until forced, then pick the best option. Elegant.

But can you write it from scratch under interview pressure? The details trip people up: appending the target as a dummy station, negating for max-heap behavior, checking fuel < 0 after the while loop to detect impossibility. These are the kinds of things that feel obvious when reading but get muddled when writing.

Spaced repetition locks them in. You write the greedy-heap loop from memory at increasing intervals. After a few rounds, the pattern is automatic. You see "minimum stops" or "minimum interventions" and the code flows out without hesitation.

The lazy-greedy-with-heap pattern alone covers a significant number of hard LeetCode problems. Learning it once and drilling it with spaced repetition is far more effective than re-solving each problem from scratch.

Related posts

• Gas Station - A greedy one-pass problem on a circular route where reset logic replaces the heap
• Jump Game - Greedy farthest-reach tracking on an array (boolean reachability)
• Jump Game II - Minimum jumps with greedy BFS level tracking
• Koko Eating Bananas - Binary search on answer space to minimize a resource
• Candy - Two-pass greedy to satisfy neighbor constraints

CodeBricks breaks the minimum refueling stops problem into its lazy-greedy and max-heap building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a "minimize interventions" problem shows up in your interview, you do not think about it. You just write it.