Minimum Number of Refueling Stops

Hard Heaps Advanced Original on LeetCode

Minimum Number of Refueling Stops is a hard heaps problem solved with the advanced pattern. The best approach, optimal (max-heap of passed stations), runs in O(n log n) time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from dynamic programming (farthest reach per stop count) up.

Problem

A car starts at mile 0 with startFuel liters in an unlimited tank and wants to reach mile target. It burns exactly one liter per mile. Along the road there are gas stations, given as stations[i] = [position_i, fuel_i] in increasing order of position: stopping at station i adds fuel_i liters to the tank.

Return the fewest stops needed to reach target, or -1 if it cannot be done. Arriving somewhere (a station or the target) with exactly 0 liters left still counts as arriving.

Examples

Example 1

Input
target = 50, startFuel = 20, stations = [[10, 15], [25, 30], [40, 5]]
Output
2
Why
Fill up at mile 10 (fuel reaches 35 miles), then at mile 25 (fuel reaches 65 miles), which covers mile 50.

Example 2

Input
target = 30, startFuel = 5, stations = [[10, 40]]
Output
-1
Why
The car runs dry at mile 5 and never reaches the only station at mile 10.

Example 3

Input
target = 12, startFuel = 12, stations = [[3, 7], [8, 2]]
Output
0
Why
The starting tank already covers the whole trip.

Constraints

  • 1 <= target, startFuel <= 10^9
  • 0 <= stations.length <= 500
  • 1 <= position_i < position_{i+1} < target
  • 1 <= fuel_i < 10^9

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Dynamic programming (farthest reach per stop count)O(n²)O(n)
Optimal (max-heap of passed stations)O(n log n)O(n)

1Dynamic programming (farthest reach per stop count)

TimeO(n²)For each of the n stations we update up to n stop counts.
SpaceO(n)One array of n + 1 reaches.

Let reach[k] be the farthest mile the car can get to using exactly k stops among the stations seen so far. Process stations left to right; for station i, every count k whose reach already gets to that station can be extended to k + 1 stops by adding its fuel. Iterate k downwards so each station is used at most once. The answer is the smallest k with reach[k] >= target.

  1. Create reach of size n + 1, reach[0] = startFuel, the rest 0.
  2. For each station i (position p, fuel f): for k from i down to 0, if reach[k] >= p then reach[k + 1] = max(reach[k + 1], reach[k] + f).
  3. Return the first k with reach[k] >= target, or -1.
class Solution {
    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        int n = stations.length;
        long[] reach = new long[n + 1];
        reach[0] = startFuel;
        for (int i = 0; i < n; i++) {
            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;
    }
}

2Optimal (max-heap of passed stations)

TimeO(n log n)Each station is pushed and popped at most once, each heap operation costs O(log n).
SpaceO(n)The heap can hold every station.

Drive as far as the tank allows and push the fuel of every station you pass into a max-heap. Whenever the tank cannot reach the next station (or the target), retroactively take the biggest fuel amount from the heap: that is one stop, and it is the stop that helps the most. If the heap is empty when you are stuck, the target is unreachable.

  1. Let reach = startFuel, stops = 0, i = 0, and an empty max-heap.
  2. While reach < target: push the fuel of every station with position <= reach (advancing i).
  3. If the heap is empty, return -1; otherwise reach += heap.pop() and stops++.
  4. Return stops.
class Solution {
    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
        long reach = startFuel;
        int stops = 0, i = 0, n = stations.length;
        while (reach < target) {
            while (i < n && stations[i][0] <= reach) {
                heap.offer(stations[i][1]);
                i++;
            }
            if (heap.isEmpty()) return -1;
            reach += heap.poll();
            stops++;
        }
        return stops;
    }
}

Edge cases to test

  • No stations at all: the answer is 0 or -1
  • The start fuel already reaches the target
  • Arriving at a station with exactly 0 fuel still lets you refuel there
  • A gap between two stations that no choice of stops can cross
  • Fuel sums larger than 2^31 - 1 (use 64-bit counters)

Hints

Hint 1

You never need to decide at the moment you pass a station. You can decide later, as if you had taken its fuel back then.

Hint 2

When the tank runs out, which already-passed station would you most like to have stopped at?

Hint 3

Keep the fuel amounts of passed stations in a max-heap and pop the largest each time you would run dry.

FAQ

What is the best time complexity for Minimum Number of Refueling Stops?

Optimal (max-heap of passed stations) runs in O(n log n) time and O(n) extra space. Each station is pushed and popped at most once, each heap operation costs O(log n).

Which pattern does Minimum Number of Refueling Stops use?

It is a heaps problem that uses the advanced pattern. Other problems with the same pattern: Find K Pairs with Smallest Sums, Find Median from Data Stream, Trapping Rain Water II.

Is there a brute force solution for Minimum Number of Refueling Stops?

Yes. Dynamic programming (farthest reach per stop count) takes O(n²) time and O(n) space. Let reach[k] be the farthest mile the car can get to using exactly k stops among the stations seen so far.

Which edge cases should I test for Minimum Number of Refueling Stops?

No stations at all: the answer is 0 or -1; The start fuel already reaches the target; Arriving at a station with exactly 0 fuel still lets you refuel there; A gap between two stations that no choice of stops can cross; Fuel sums larger than 2^31 - 1 (use 64-bit counters).