Minimum Number of Refueling Stops [Hard] — Greedy Max-Heap + DP

Problem Statement#

You start at position 0 with startFuel litres of fuel. A car uses one litre per unit of distance travelled. You are given a sorted array stations where stations[i] = [position_i, fuel_i], meaning there is a refuelling station at position_i that can add fuel_i litres to your tank. You may stop at any station or skip it entirely.

Return the minimum number of refuelling stops needed to reach target. If it is impossible, return -1.

Example 1 (the classic walkthrough case):

Input:  target = 100, startFuel = 10
        stations = [[10, 60], [20, 30], [30, 30], [60, 40]]
Output: 2

Example 2 (easy reach):

Input:  target = 1, startFuel = 1, stations = []
Output: 0

Example 3 (impossible):

Input:  target = 100, startFuel = 1, stations = [[10, 100]]
Output: -1   (can't even reach the first station)

Constraints (from LeetCode):

• 1 <= target, startFuel <= 10^9
• 0 <= stations.length <= 500
• 0 <= position_i <= target
• 1 <= fuel_i <= 10^9
• Stations are given in strictly increasing order of position.

Why This Problem Matters#

LC 871 is an Amazon favourite — it sits at the intersection of greedy algorithms and heap usage, two areas the team cares deeply about. It also has a clean DP formulation that tests whether you can derive a state transition from scratch rather than pattern-match a template.

More broadly, this problem is a gateway to a family of "lazy evaluation" greedy problems. The core idea — collect options as you pass them, defer the decision until you actually need them, then pick the best option available — appears in task scheduling (LC 630 Course Schedule III), stock trading (LC 122 Best Time to Buy and Sell Stock II), and jump games (LC 45 Jump Game II). Mastering the greedy heap insight here pays dividends across many Hard problems.

In an interview setting, a candidate who can both implement the greedy and explain the DP — plus articulate why the greedy works without just saying "because greedy" — is demonstrating exactly the depth that Amazon and Google look for. This post gives you all three pieces: the intuition, the proof sketch, and the code.

The Greedy Max-Heap Insight#

The Core Observation#

Imagine you are driving toward a distant target. You drive as far as your fuel allows, passing multiple stations along the way. When your tank hits zero and you are stuck short of the next waypoint, you need to retroactively decide: which one of the stations I already passed should I have stopped at?

The answer is greedy and simple: stop at the one that would have given you the most fuel, because that maximises how far you can drive before getting stuck again. You do not need to decide in advance — you collect all the fuel amounts you have passed, and when you need fuel, you draw from the largest available.

A max-heap (priority queue) is the perfect data structure for this: inserting a station's fuel amount is O(log n), and extracting the maximum is also O(log n). Python's heapq module is a min-heap, so we negate the values to simulate a max-heap.

Why This Greedy Is Correct#

Claim: Always taking the maximum available fuel when forced to refuel never produces a worse result than any other choice.

Intuition: Suppose the optimal solution stops at station A (not the maximum) when forced to refuel. Could we swap A for station B (the maximum, with fuel_B >= fuel_A)? Yes — the swap can only give us more or equal fuel, which means we can travel at least as far. Therefore the greedy choice of maximum fuel is at least as good as any other choice. This exchange argument holds inductively for each stop made.

The Algorithm Step by Step#

1. Sweep through stations from left to right, keeping a fuel counter.
2. Whenever you successfully reach a station, push its fuel amount into the max-heap (as a future option). Do not count this as a stop — you are just making the fuel available.
3. After processing each station's position, check: can you reach the next station (or the target)? If fuel >= next_position, you are fine — move on.
4. If fuel < next_position, you are stuck. Greedily pull from the max-heap: pop the largest fuel available, add it to your tank, and increment the stop counter. Repeat until you can reach the next position or the heap is empty.
5. If the heap is empty and you still cannot reach the next position, return -1.

This sweep naturally handles skipped stations — they are "available in the heap" but never popped until needed.

Visual Dry Run#

Let us trace through Example 1 step by step.

target = 100, startFuel = 10
stations = [[10, 60], [20, 30], [30, 30], [60, 40]]
 
Treat target as a virtual final station with 0 fuel:
effective stations = [[10,60], [20,30], [30,30], [60,40], [100,0]]
 
Initial state:
  fuel = 10, stops = 0, heap = []
 
─── Station [10, 60] ───────────────────────────────
  Can we reach position 10?  fuel=10 >= 10  YES
  Push 60 into heap.
  heap = [60]  (max at top)
 
─── Station [20, 30] ───────────────────────────────
  Can we reach position 20?  fuel=10 < 20  NO → STUCK
    Pop 60 from heap, fuel = 10 + 60 = 70, stops = 1
    heap = []
  Can we reach position 20?  fuel=70 >= 20  YES
  Push 30 into heap.
  heap = [30]
 
─── Station [30, 30] ───────────────────────────────
  Can we reach position 30?  fuel=70 >= 30  YES
  Push 30 into heap.
  heap = [30, 30]
 
─── Station [60, 40] ───────────────────────────────
  Can we reach position 60?  fuel=70 >= 60  YES
  Push 40 into heap.
  heap = [40, 30, 30]
 
─── Virtual station [100, 0] ───────────────────────
  Can we reach position 100?  fuel=70 < 100  NO → STUCK
    Pop 40 from heap, fuel = 70 + 40 = 110, stops = 2
    heap = [30, 30]
  Can we reach position 100?  fuel=110 >= 100  YES
  Push 0 into heap (doesn't matter).
 
All stations processed. stops = 2.
Output: 2  ✓

Notice that we stopped at station at position 10 (60 litres) and station at position 60 (40 litres) — the two largest fuel amounts among all stations we passed. The stations at positions 20 and 30 were skipped. The greedy heap found this automatically without any lookahead.

Common Mistakes#

Mistake 1: Forgetting to Add the Target as a Virtual Station#

Without a sentinel at target, you would need special-case logic to check whether you can reach the target after the last station. Adding [target, 0] to the stations list turns the loop uniform — the check "can I reach this position?" handles the final stretch automatically, just like any intermediate station.

If you skip this, you will often get a correct answer on simple test cases but fail when the last real station is far from the target, because the stuck-check never triggers for the final leg.

Mistake 2: Checking Fuel Relative to Position Rather Than Fuel Remaining#

A very common bug is to check fuel < pos but forget that fuel is an absolute tank size, not a delta. In this problem the tank starts with startFuel and you add to it at stops. The position check must compare the running fuel value (total fuel ever added minus distance burned, which equals the starting value minus distance because fuel equals distance 1:1) against the position. Because 1 unit of fuel = 1 unit of distance, fuel directly represents how far you can still travel from position 0 — so fuel < next_pos is exactly the right stuck condition.

Mistake 3: Counting the Push as a Stop#

When you arrive at a station and push its fuel into the heap, that is not a stop. You are only registering it as an option. The stop is counted when you pop from the heap (i.e., when you actually decide to have refuelled there). Counting pushes as stops leads to overcounting and wrong answers.

Mistake 4: Neglecting the Impossible Case in the DP Approach#

In the DP solution, dp[k] represents the farthest you can reach using exactly k stops. When initialising, only dp[0] = startFuel is valid — all other entries should be -infinity (or 0 if you handle the impossible check differently). Failing to initialise correctly means you may "reach" positions with zero stops when you actually need at least one, corrupting the answer.

Mistake 5: Off-by-One When Iterating Stations in DP#

The DP updates must iterate k from i down to 0 (reverse order) to avoid using the same station twice in one row's update. This is the same pattern as the 0/1 Knapsack problem. Iterating forward would allow the same station to be counted multiple times in a single sweep.

Solutions#

Approach 1: Greedy Max-Heap — O(n log n) Time, O(n) Space#

This is the preferred interview solution. It is faster, more space-efficient, and the greedy insight is a compelling talking point.

Python#

import heapq
from typing import List
 
class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        # Add the target as a virtual station with 0 fuel.
        # This lets the main loop handle the final leg uniformly
        # without special-case code after the loop.
        stations.append([target, 0])
 
        # max_heap stores negated fuel amounts (Python heapq is a min-heap,
        # so negating turns it into a max-heap).
        max_heap = []
 
        fuel = startFuel   # current fuel in the tank (also = max reachable position)
        stops = 0          # number of refuelling stops taken so far
 
        for pos, cap in stations:
            # While we cannot reach this station's position, we are stuck.
            # Greedily draw from the largest fuel we have passed so far.
            while fuel < pos:
                if not max_heap:
                    # Heap is empty — no previously passed station can save us.
                    return -1
 
                # Pop the largest available fuel (negated, so add negative = subtract)
                fuel += -heapq.heappop(max_heap)   # e.g. heap has -60, pop gives -60, negate = +60
                stops += 1                          # we retroactively stopped there
 
            # We can reach this station. Register its fuel as an option for later.
            # We do NOT count this as a stop — it is just made available.
            heapq.heappush(max_heap, -cap)          # negate to maintain max-heap property
 
        return stops

JavaScript#

/**
 * Greedy Max-Heap solution for LC 871.
 *
 * JavaScript does not have a built-in priority queue, so we implement
 * a simple max-heap class. In a real interview you can ask the interviewer
 * if a PQ is available; if not, implement the key operations inline.
 *
 * @param {number} target
 * @param {number} startFuel
 * @param {number[][]} stations
 * @return {number}
 */
var minRefuelStops = function(target, startFuel, stations) {
    // Append the target as a virtual final station with 0 fuel.
    stations.push([target, 0]);
 
    // Max-heap backed by an array.
    // We only need push (insert) and pop (extract-max) operations.
    const heap = [];
 
    // Heap helper: swap elements
    const swap = (i, j) => { [heap[i], heap[j]] = [heap[j], heap[i]]; };
 
    // Sift up after inserting at the end (maintains max-heap invariant)
    const push = (val) => {
        heap.push(val);
        let i = heap.length - 1;
        while (i > 0) {
            const parent = Math.floor((i - 1) / 2);
            if (heap[parent] >= heap[i]) break;   // already in order
            swap(i, parent);
            i = parent;
        }
    };
 
    // Sift down after moving root to end (maintains max-heap invariant)
    const pop = () => {
        const top = heap[0];                       // save the maximum
        const last = heap.pop();                   // remove last element
        if (heap.length > 0) {
            heap[0] = last;                        // put last element at root
            let i = 0;
            while (true) {
                const left = 2 * i + 1;
                const right = 2 * i + 2;
                let largest = i;
                if (left < heap.length && heap[left] > heap[largest]) largest = left;
                if (right < heap.length && heap[right] > heap[largest]) largest = right;
                if (largest === i) break;          // heap invariant restored
                swap(i, largest);
                i = largest;
            }
        }
        return top;
    };
 
    let fuel = startFuel;   // total fuel currently in tank
    let stops = 0;          // refuelling stops taken
 
    for (const [pos, cap] of stations) {
        // While we cannot reach this position, pull the best option available.
        while (fuel < pos) {
            if (heap.length === 0) {
                // No previously passed station can save us — impossible.
                return -1;
            }
            fuel += pop();   // retroactively stop at the largest-fuel station passed
            stops++;
        }
 
        // We reached this station. Add its fuel as a future option.
        // This is NOT counted as a stop.
        push(cap);
    }
 
    return stops;
};

Approach 2: Dynamic Programming — O(n²) Time, O(n) Space#

This approach is worth knowing for two reasons: it sometimes appears in follow-up questions, and the derivation demonstrates strong DP fundamentals. The state is:

dp[k] = the farthest position reachable using exactly k refuelling stops.

Transition: For each station i with position p and fuel f:

• If we can already reach station i using k stops (dp[k] >= p), then we can optionally stop there, reaching dp[k] + f using k+1 stops.
• dp[k+1] = max(dp[k+1], dp[k] + f)

We iterate stations in order and update dp in reverse (like 0/1 Knapsack) to avoid using station i more than once per row.

Answer: The minimum k such that dp[k] >= target.

Python#

from typing import List
 
class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        n = len(stations)
 
        # dp[k] = farthest position reachable with exactly k stops.
        # We size it n+1 because with n stations the max stops is n.
        dp = [0] * (n + 1)
        dp[0] = startFuel   # with 0 stops we can reach startFuel distance
 
        for i, (pos, fuel) in enumerate(stations):
            # Iterate k in reverse to avoid counting station i twice
            # in the same DP update pass (same trick as 0/1 Knapsack).
            for k in range(i, -1, -1):
                if dp[k] >= pos:
                    # We can reach station i using k stops.
                    # Optionally stop here: now we can reach dp[k] + fuel with k+1 stops.
                    dp[k + 1] = max(dp[k + 1], dp[k] + fuel)
 
        # Find the minimum k such that we can reach or exceed target.
        for k, reach in enumerate(dp):
            if reach >= target:
                return k   # k is the answer: minimum stops
 
        return -1   # target is unreachable

JavaScript#

/**
 * Dynamic Programming solution for LC 871.
 *
 * dp[k] = farthest position reachable using exactly k refuelling stops.
 *
 * @param {number} target
 * @param {number} startFuel
 * @param {number[][]} stations
 * @return {number}
 */
var minRefuelStops = function(target, startFuel, stations) {
    const n = stations.length;
 
    // Initialise dp array. dp[0] = startFuel (reach startFuel with 0 stops).
    // All other dp[k] start at 0 — we haven't found a way to make k stops yet.
    const dp = new Array(n + 1).fill(0);
    dp[0] = startFuel;
 
    for (let i = 0; i < n; i++) {
        const [pos, fuel] = stations[i];
 
        // Iterate k from i down to 0 (reverse order, same as 0/1 Knapsack).
        // This prevents station i from being counted more than once per pass.
        for (let k = i; k >= 0; k--) {
            if (dp[k] >= pos) {
                // We can reach station i using k stops.
                // If we also stop here, we get dp[k] + fuel distance with k+1 stops.
                dp[k + 1] = Math.max(dp[k + 1], dp[k] + fuel);
            }
        }
    }
 
    // The answer is the smallest k such that dp[k] >= target.
    for (let k = 0; k <= n; k++) {
        if (dp[k] >= target) return k;
    }
 
    return -1;   // unreachable
};

Complexity Analysis#

For n = 500 (the constraint ceiling), the DP runs about 125,000 operations — well within limits. The greedy runs about 4,500 operations. Both pass comfortably. In an interview, lead with the greedy for its better complexity and cleaner story; mention the DP as a "backup derivation" you can switch to if asked.

The space for the greedy is O(n) in the worst case (all stations pushed to heap before any pop). The DP is also O(n) for the dp array.

Follow-up Questions#

LC 45 — Jump Game II#

Connection: Both problems ask for the minimum number of "jumps" to reach a goal, and both have optimal greedy solutions. In Jump Game II, at each position you have a jump range; you greedily extend to the farthest reachable point before incrementing the jump count. In Refuelling Stops, you have a fuel tank; you greedily refuel with the largest available fuel before incrementing the stop count. The structure is identical: collect reachable options, defer the decision, pick the best when forced.

Interview follow-up to expect: "Can you solve LC 45 in O(n) without a heap?" Yes — because jump ranges are known at each position without needing to retroactively pick, so a simple greedy sweep with a running maximum suffices. Refuelling Stops needs a heap because the fuel amounts at passed stations are all candidates, not just the current maximum reach.

LC 134 — Gas Station#

Connection: Gas Station asks whether you can complete a circular route, and if so, from which starting index. It uses the same "accumulate surplus/deficit" observation: if total gas exceeds total cost, a valid starting point always exists. The greedy here is about which starting station to choose, not which stations to stop at.

Key difference: Gas Station is a single-pass O(n) greedy with no heap. Refuelling Stops requires retroactively choosing which stations to stop at, making the heap necessary. A good interviewer may ask you to contrast the two — the answer is that Gas Station has a clean local greedy (restart when deficit goes negative), while Refuelling Stops needs a global view of past options.

Follow-up question to expect: "What if fuel tanks have a maximum capacity?" Now a greedy on the largest past station may not be valid — you might overflow the tank. This turns into a more complex optimisation where you must balance the gains from large fuel dumps against the tank ceiling. The problem becomes significantly harder and may require DP.

This Pattern Solves#

The unifying thread: you encounter options sequentially, you do not know the optimal choice at encounter time, so you store all options and defer the decision until forced — then pick the local best. This deferred greedy works whenever the order in which you consume options does not affect feasibility (i.e., taking a larger option now does not block a smaller option later).

Key Takeaways#

• The greedy insight: drive as far as possible; when the tank hits 0, retroactively refuel at the largest station you passed (max-heap).
• A max-heap stores fuel amounts of all passed stations; pop the maximum whenever you get stuck — this is the greedy deferred-choice pattern.
• O(n log n) time for the greedy approach (each station pushed and popped at most once from the heap).
• The DP alternative: dp[k] = farthest reachable position with exactly k stops; update right to left per station. O(n^2) time, O(n) space.
• Return -1 if the heap is empty when the tank runs dry — no reachable station can save you.
• The key trigger phrase for this pattern: "optional resources along a path, minimize how many you use" — examples include LC 630 (Course Schedule III) and LC 1642 (Furthest Building).
• The deferred greedy is correct by an exchange argument: swapping the heap's max stop with any other stop never increases the number of stops needed.