Minimum Refueling Stops — Greedy Max-Heap Interview

Problem Statement#

A car travels from 0 to target with startFuel units. It passes stations along the way; stations[i] = [position, fuel]. The car burns 1 unit per mile. Return the minimum number of stops to reach the target, or -1 if impossible.

Constraints:

• 1 <= target, startFuel <= 10^9
• 0 <= stations.length <= 500
• Stations strictly increasing in position.

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

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

Why This Problem Matters#

LeetCode 871 is a hard interview problem at Amazon, Google, and Microsoft. It teaches a deep greedy insight: you do not commit to refueling at a station when you pass it; you defer the decision and "retroactively" refuel at the richest unused station only when you run out.

This pattern, often called "regret greedy" or "deferred greedy," is one of the highest-leverage tricks in heap FAANG interview prep. It appears in scheduling, profit-maximizing, and even genetic algorithms.

The Core Insight#

Push every station you pass into a max-heap (by fuel). Whenever your fuel cannot reach the next stop or target, pop the largest fuel from the heap and add it. If the heap is empty when you need fuel, return -1. The answer is the number of pops.

Visual Dry Run#

target=100, startFuel=10, stations=[[10,60],[20,30],[30,30],[60,40]]

Solution (Optimal)#

import heapq
from typing import List
 
class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        heap = []  # max-heap via negation
        stops = 0
        fuel = startFuel
        i = 0
        n = len(stations)
        while fuel < target:
            while i < n and stations[i][0] <= fuel:
                heapq.heappush(heap, -stations[i][1])
                i += 1
            if not heap:
                return -1
            fuel += -heapq.heappop(heap)
            stops += 1
        return stops

class MaxHeap {
    constructor() { this.h = []; }
    push(v) { this.h.push(v); this._up(this.h.length - 1); }
    pop() {
        const top = this.h[0], last = this.h.pop();
        if (this.h.length) { this.h[0] = last; this._down(0); }
        return top;
    }
    _up(i) {
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[i] > this.h[p]) { [this.h[i], this.h[p]] = [this.h[p], this.h[i]]; i = p; }
            else break;
        }
    }
    _down(i) {
        const n = this.h.length;
        while (true) {
            const l = 2 * i + 1, r = 2 * i + 2;
            let m = i;
            if (l < n && this.h[l] > this.h[m]) m = l;
            if (r < n && this.h[r] > this.h[m]) m = r;
            if (m === i) break;
            [this.h[i], this.h[m]] = [this.h[m], this.h[i]];
            i = m;
        }
    }
    get size() { return this.h.length; }
}
 
var minRefuelStops = function(target, startFuel, stations) {
    const heap = new MaxHeap();
    let stops = 0, fuel = startFuel, i = 0;
    while (fuel < target) {
        while (i < stations.length && stations[i][0] <= fuel) {
            heap.push(stations[i][1]);
            i++;
        }
        if (heap.size === 0) return -1;
        fuel += heap.pop();
        stops++;
    }
    return stops;
};

Time: O(N log N) — each station enters and leaves the heap at most once. Space: O(N) — heap can hold all stations in the worst case.

Common Mistakes#

• Greedy by position (refuel at every station) — wrong; you may waste stops.
• Greedy by largest fuel ahead — fails because you cannot see beyond reachable range.
• Forgetting to check heap empty — leads to false positives when target is unreachable.
• Comparing <= fuel vs < fuel for station inclusion — must be <= because the station at exactly fuel is reachable.
• Treating it as DP — possible but O(N^2) and slower.

Interview Tips#

• Pitch it as "regret greedy" — explain the deferred decision verbally.
• Walk through why a simple greedy "take every station" or "take the closest big one" fails.
• Show the DP solution as an alternative for the interviewer who wants to see breadth.
• Mention that this is the same pattern as IPO (LeetCode 502) and Maximum Performance of a Team.

Follow-up Questions#

• What if some stations have a refuel cost? Hint: 2D max-heap by net gain.
• What if the car has limited fuel capacity? Hint: heap entries also track time of acceptance.
• What about minimum fuel cost, not minimum stops? Hint: classic Dijkstra on station graph.
• What if stations can run out (capacity)? Hint: each station entry has (fuel, capacity).
• Online version: stations stream in. Hint: same algorithm, just buffer.

Key Takeaways#

• LeetCode 871 Minimum Refueling Stops is a regret-greedy max-heap problem.
• Push reachable stations into a max-heap; pop only when you need fuel.
• Time: O(N log N). Space: O(N).
• The heap defers the refueling decision until it is forced.
• Returns -1 cleanly when no station can extend the journey.
• This deferred-greedy pattern reuses for IPO, Maximum Performance of a Team, and Profit Maximization.
• A staple Amazon and Google priority queue interview question.