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.
- 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 <= 10000000000 <= stations.length <= 5000 < position_i <= position_{i+1} < target1 <= fuel_i < 1000000000
Hints for Minimum Number of Refueling Stops
Hint 1
You do not have to decide to stop when you pass a station — you can decide retroactively.
Hint 2
Drive as far as the fuel allows, collecting the passed stations into a max-heap.
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
- Track the furthest reachable position
fuel(the car starts at 0). - Push every station at or before
fuelinto 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.
fueltracks 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 >= targetand-1otherwise.
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 stopsJava
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