Minimum Number of Refueling Stops — Hard Problem & Solution

A car drives from position 0 to position target with infinite tank capacity, starting with startFuel litres and using one litre per unit of distance.

Difficulty: Hard
Topics: Arrays, Dynamic Programming, Greedy, Heap
Asked at: Amazon, Google, Uber
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A car drives from position 0 to position target with infinite tank capacity, starting with startFuel litres and using one litre per unit of distance.

stations[i] = [position_i, fuel_i] lists the gas stations in increasing order of position; stopping at one transfers all its fuel into the tank. Return the minimum number of stops needed to reach the target, or -1 if it is impossible.

Example 1

Input: target = 1, startFuel = 1, stations = [[5,100]]
Output: 0
Explanation: The car already has enough fuel.

Example 2

Input: target = 100, startFuel = 1, stations = [[10,100]]
Output: -1
Explanation: The car cannot even reach the first station.

Example 3

Input: target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
Output: 2
Explanation: Refuel at positions 10 and 60.

Constraints

1 <= target, startFuel <= 1000000000
0 <= stations.length <= 500
0 < position_i <= position_{i+1} < target
1 <= fuel_i < 1000000000

How to solve Minimum Number of Refueling Stops

Defer the decision. Drive forward, remembering every station passed in a max-heap keyed on fuel. When the tank cannot reach further, retroactively refuel at the biggest station already passed — that is always the best single stop to have made.

Approach

Track the furthest reachable position fuel (the car starts at 0).
Push every station at or before fuel into a max-heap.
While fuel < target, pop the largest fuel amount, add it, and count a stop; if the heap is empty the target is unreachable.

Why it works

Exchange argument: if an optimal solution uses m stops, then after any prefix of driving, the greedy's reachable distance is at least the optimal's — because the greedy has always taken the j largest fuel amounts among the stations passed, which dominates any other choice of j. So the greedy never needs more stops.

Complexity

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

Pitfalls

Deciding at each station whether to stop, without look-ahead, is wrong — the choice depends on what comes later.
fuel tracks the furthest reachable position, not the litres left in the tank; they coincide because one litre covers one unit.
An empty station list is legal; the answer is 0 when startFuel >= target and -1 otherwise.

Reference solution

Python

import heapq
from typing import List

def minRefuelStops(target: int, startFuel: int, stations: List[List[int]]) -> int:
    heap = []
    fuel, stops, i = startFuel, 0, 0
    while fuel < target:
        while i < len(stations) 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

JavaScript

var minRefuelStops = function(target, startFuel, stations) {
    var heap = [];
    var push = function(v) {
        heap.push(v);
        var i = heap.length - 1;
        while (i > 0) {
            var p = (i - 1) >> 1;
            if (heap[p] >= heap[i]) break;
            var tmp = heap[p]; heap[p] = heap[i]; heap[i] = tmp;
            i = p;
        }
    };
    var pop = function() {
        var top = heap[0];
        var last = heap.pop();
        if (heap.length > 0) {
            heap[0] = last;
            var i = 0;
            while (true) {
                var l = 2 * i + 1, r = 2 * i + 2, m = i;
                if (l < heap.length && heap[l] > heap[m]) m = l;
                if (r < heap.length && heap[r] > heap[m]) m = r;
                if (m === i) break;
                var tmp2 = heap[m]; heap[m] = heap[i]; heap[i] = tmp2;
                i = m;
            }
        }
        return top;
    };
    var fuel = startFuel, stops = 0, j = 0;
    while (fuel < target) {
        while (j < stations.length && stations[j][0] <= fuel) { push(stations[j][1]); j++; }
        if (heap.length === 0) return -1;
        fuel += pop();
        stops++;
    }
    return stops;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue