Minimum Number of Refueling Stops

HardGreedy · Heap (Priority Queue) · DP🧩 Greedy LeetCode #871 ↗Updated Oct 30, 2026

Problem

A car drives east from position 0 towards target, starting with startFuel litres and burning one litre per mile. Along the way, stations[i] = [position, fuel] (sorted by position) each offer a fixed amount of fuel; stopping takes all of it. Return the fewest stops needed to reach target, or -1 if it cannot be reached. Arriving with exactly 0 fuel still counts as arriving.

Inputtarget = 1, startFuel = 1, stations = []Output0

Inputtarget = 100, startFuel = 1, stations = [[10,100]]Output-1

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

1 ≤ target, startFuel ≤ 10⁹ · 0 ≤ stations.length ≤ 500 · 1 ≤ position_i < position_i+1 < target · 1 ≤ fuel_i < 10⁹

Try it yourself

Java

class Solution {
    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

You don't have to decide at a station whether to stop. Drive as far as you can, remembering every station you passed; when you run dry, pretend you stopped at the richest one you skipped. A max-heap makes that “retroactive” choice cheap.

PatternGreedy

Instinct An optimisation where one obvious local rule (earliest end, farthest reach, biggest first) never needs undoing - commit to it, then try hard to break it.

Memory hack Grab the best bite now and never look back - but only once a counterexample hunt fails to make you regret it.

Open the Greedy guide →

Approaches

Brute ForceTry Every Stop / Skip Combination

Time O(2ⁿ)Space O(n)

Since fuel left = (start fuel + fuel collected) − position, the state is just the farthest reachable point. At each reachable station branch on “stop” or “skip” and keep the fewest stops among branches that reach target.

Java

public int minRefuelStops(int target, int startFuel, int[][] stations) {
    int best = explore(target, stations, 0, startFuel, 0);
    return best == Integer.MAX_VALUE ? -1 : best;
}

// reach = farthest point the fuel collected so far can carry us
private int explore(int target, int[][] stations, int i, long reach, int stops) {
    if (reach >= target) return stops;
    if (i == stations.length || stations[i][0] > reach) return Integer.MAX_VALUE;
    int stop = explore(target, stations, i + 1, reach + stations[i][1], stops + 1);
    int skip = explore(target, stations, i + 1, reach, stops);
    return Math.min(stop, skip);
}

Obviously correct, but exponential — only for tiny inputs.

BetterDP — Farthest Reach with k Stops

Time O(n²)Space O(n)

Let reach[k] be the farthest point reachable using k stops among the stations seen so far. Station i can extend reach[k] to reach[k+1] only if reach[k] ≥ position. Iterate k downward (0/1-knapsack style) so each station is used once; the answer is the smallest k with reach[k] ≥ target.

Java

public int minRefuelStops(int target, int startFuel, int[][] stations) {
    int n = stations.length;
    long[] reach = new long[n + 1]; // reach[k] = farthest point using k stops
    reach[0] = startFuel;
    for (int i = 0; i < n; i++) {
        // go downward so station i is counted at most once
        for (int k = i; k >= 0; k--) {
            if (reach[k] >= stations[i][0]) {
                reach[k + 1] = Math.max(reach[k + 1], reach[k] + stations[i][1]);
            }
        }
    }
    for (int k = 0; k <= n; k++) {
        if (reach[k] >= target) return k;
    }
    return -1;
}

Polynomial and clean, but quadratic in the number of stations.

OptimalGreedy + Max-Heap of Passed Stations

Time O(n log n)Space O(n)

Drive until the tank can't reach the next station (or the target), pushing the fuel of every station passed onto a max-heap. When stuck, “stop” retroactively at the largest unused one: if any stop works, taking the biggest is never worse. An empty heap while stuck means the target is unreachable.

Java

public int minRefuelStops(int target, int startFuel, int[][] stations) {
    PriorityQueue<Integer> passed = new PriorityQueue<>(Collections.reverseOrder());
    long reach = startFuel;
    int stops = 0, i = 0;
    while (reach < target) {
        // bank every station the current fuel already reaches
        while (i < stations.length && stations[i][0] <= reach) {
            passed.offer(stations[i][1]);
            i++;
        }
        if (passed.isEmpty()) return -1;
        reach += passed.poll(); // refuel at the richest station we skipped
        stops++;
    }
    return stops;
}

Dry runtarget = 1, startFuel = 1, stations = []

i next station changed

start
60
i
30

30

40

reach = 10
bank
60

30
i
30

40

pos 10 ≤ 10: heap {60}
stop 1
·

30
i
30

40

take 60 → reach 70
bank
·

30

30

40

heap {40,30,30}
stop 2
·

30

30

·

take 40 → 110 ✔

Each station is pushed and popped at most once — the intended solution.

Pro tip

Keep reach as a long: summing several fuels near 10⁹ overflows int.

At a glance

Level	Approach	Time	Space
Brute Force	Try Every Stop / Skip Combination	`O(2ⁿ)`	`O(n)`
Better	DP — Farthest Reach with k Stops	`O(n²)`	`O(n)`
Optimal	Greedy + Max-Heap of Passed Stations	`O(n log n)`	`O(n)`

Common pitfalls

Greedily stopping at every station you reach — wastes stops.
Running the DP inner loop upward — reuses the same station twice.
Using int for total reach — overflows with large fuel values.

Interview tips

Reframe state as “farthest reachable point” — fuel left is implied.
Present the DP first, then argue why the biggest skipped station is always a safe pick.
Mention the same “regret with a heap” trick in Course Schedule III.

Pattern

Greedy with regret (heap) → when you can postpone a choice and later grab the best option already passed.

My notes saved in this browser