Minimum Number of Refueling Stops

Hard
867.

Minimum Number of Refueling Stops

Minimum Number of Refueling Stops is a hard coding problem on arrays, dynamic programming and greedy, asked in Amazon, Google and Uber interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} target
 * @param {number} startFuel
 * @param {number[][]} stations
 * @return {number}
 */
var minRefuelStops = function(target, startFuel, stations) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Number of Refueling Stops — Problem & Solution

Minimum Number of Refueling Stops solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Minimum Number of Refueling Stops is a hard coding problem on arrays, dynamic programming and greedy, asked in Amazon, Google and Uber interviews.

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

Hints for Minimum Number of Refueling Stops

  1. Hint 1

    You do not have to decide to stop when you pass a station — you can decide retroactively.

  2. Hint 2

    Drive as far as the fuel allows, collecting the passed stations into a max-heap.

  3. Hint 3

    When you run short, 'go back' and take the largest fuel amount you passed.

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

  1. Track the furthest reachable position fuel (the car starts at 0).
  2. Push every station at or before fuel into a max-heap.
  3. 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

Java

public static int minRefuelStops(int target, int startFuel, int[][] stations) {
    PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
    long fuel = startFuel;
    int stops = 0, i = 0;
    while (fuel < target) {
        while (i < stations.length && stations[i][0] <= fuel) {
            heap.offer(stations[i][1]);
            i++;
        }
        if (heap.isEmpty()) return -1;
        fuel += heap.poll();
        stops++;
    }
    return stops;
}

C++

int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
    priority_queue<int> heap;
    long long fuel = startFuel;
    int stops = 0, i = 0;
    while (fuel < target) {
        while (i < (int) stations.size() && stations[i][0] <= fuel) {
            heap.push(stations[i][1]);
            i++;
        }
        if (heap.empty()) return -1;
        fuel += heap.top();
        heap.pop();
        stops++;
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming