Minimum Number of Refueling Stops solution and explanation
Google
9 more videos on this problem
Minimum Number of Refueling Stops | Live Coding with Explanation | Leetcode - 871Algorithms Made Easy · 12:57 · 13K views
Leetcode 871 Minimum Number of Refueling Stops ||Code + Example + Explanation ||June Daily ChallengeCode with Alisha · 16:04 · 10K views
Minimum Number of Refueling Stops | Leetcode 871 | Live coding session⛽️ ⛽️ ⛽️Coding Decoded · 14:42 · 7K views
MINIMUM NUMBER OF REFUELING STOPS | LEETCODE # 871 | PYTHON SOLUTIONCracking FAANG · 19:32 · 5K views
LeetCode 871. Minimum Number of Refueling StopsHappy Coding · 38:35 · 4K views
LeetCode: Minimum Number of Refueling StopsRitambhara Coding and System Design Interviews · 7:44 · 3K views
Leetcode - Minimum Number of Refueling Stops (Python)Timothy H Chang · 7:35 · 2K views
Minimum Number of Refueling Stops | LeetCode 871 | Coders CampCoders Camp · 11:24 · 1K views
871.Minimum Number Of Refueling Stops (code solution walkthru)TechBayArea · 12:58 · 973 views
Leetcode 871 || Minimum Number of Refueling Stops || Solutioneat sleep code · 11:07 · 259 views
The problem
A car travels from a starting position to a destination which is target miles east of the starting position.
There are gas stations along the way. The gas stations are represented as an array stations where stations[i] = [positioni, fueli] indicates that the ith gas station is positioni miles east of the starting position and has fueli liters of gas.
The car starts with an infinite tank of gas, which initially has startFuel liters of fuel in it. It uses one liter of gas per one mile that it drives. When the car reaches a gas station, it may stop and refuel, transferring all the gas from the station into the car.
Return the minimum number of refueling stops the car must make in order to reach its destination. If it cannot reach the destination, return -1.
Note that if the car reaches a gas station with 0 fuel left, the car can still refuel there. If the car reaches the destination with 0 fuel left, it is still considered to have arrived.
Example 1:
Input: target = 1, startFuel = 1, stations = [] Output: 0 Explanation: We can reach the target without refueling.
Example 2:
Input: target = 100, startFuel = 1, stations = [[10,100]] Output: -1 Explanation: We can not reach the target (or even the first gas station).
Example 3:
Input: target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]] Output: 2 Explanation: We start with 10 liters of fuel. We drive to position 10, expending 10 liters of fuel. We refuel from 0 liters to 60 liters of gas. Then, we drive from position 10 to position 60 (expending 50 liters of fuel), and refuel from 10 liters to 50 liters of gas. We then drive to and reach the target. We made 2 refueling stops along the way, so we return 2.
Constraints:
1 <= target, startFuel <= 1090 <= stations.length <= 5001 <= positioni < positioni+1 < target1 <= fueli < 109
Approach overview
Problem Overview: You start with some fuel and must reach a target distance. Along the way are gas stations, each providing a fixed amount of fuel. The task is to determine the minimum number of refueling stops required to reach the target, or return -1 if the journey is impossible.
Approach 1: Dynamic Programming (O(n^2) time, O(n) space)
This method tracks the farthest distance reachable using exactly k refueling stops. Maintain a DP array where dp[k] stores the maximum distance you can travel after refueling k times. Iterate through each station and update the array backward so previous results are not overwritten. If you can reach a station with k stops, update dp[k+1] with the additional fuel from that station. After processing all stations, the smallest k where dp[k] ≥ target is the answer. This approach models the decision process clearly and works well when demonstrating state transitions using dynamic programming. The downside is quadratic time complexity for large station lists.
Approach 2: Greedy with Max Heap (O(n log n) time, O(n) space)
The optimal strategy uses a greedy idea: always refuel at the largest fuel station among those you have already passed when you run out of fuel. As you travel toward the target, push the fuel amounts of reachable stations into a max heap. When your current fuel is insufficient to move further, pop the largest fuel value from the heap and refuel. Each pop represents a refueling stop. This works because choosing the largest available refill maximizes how far you can continue without increasing the number of stops. The heap efficiently retrieves the best station in O(log n) time. This technique combines greedy algorithms with a heap (priority queue) to dynamically choose the best previous station.
Implementation typically iterates through stations sorted by distance (already provided that way). Track your current reachable distance and add stations to the heap once they become reachable. If the heap becomes empty before reaching the target, the trip is impossible.
Recommended for interviews: The greedy max heap solution is what interviewers expect. It reduces the problem to repeatedly choosing the best past option and achieves O(n log n) time. Mentioning the DP formulation first demonstrates understanding of the state space, but implementing the heap-based greedy approach shows stronger algorithmic optimization skills.
Approach 1: Greedy Approach using Max Heap
This approach leverages a greedy strategy with a max heap to ensure that whenever we're out of fuel, we choose to refuel from the station that offers the most fuel, maximizing our reach.
We traverse through the list of stations, when we reach a station, we check if we need to refuel (i.e., if our current fuel can't get us to the next station). If so, we refuel from the stations we've passed (choosing the one with the most fuel available). We keep track of the number of stops and return that as our result once we reach the target, or return -1 if it's not possible to reach the target.
from heapq import heappush, heappop
def minRefuelStops(target, startFuel, stations):
heap = []
i, stops, fuel = 0, 0, startFuel
while fuel < target:
while i < len(stations) and stations[i][0] <= fuel:
heappush(heap, -stations[i][1])
i += 1
if not heap:
return -1
fuel += -heappop(heap)
stops += 1
return stopsimport java.util.PriorityQueue;
class Solution {
public int minRefuelStops(int target, int startFuel, int[][] stations) {
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
int i = 0, n = stations.length, stops = 0;
int fuel = startFuel;
while (fuel < target) {
while (i < n && stations[i][0] <= fuel)
pq.offer(stations[i++][1]);
if (pq.isEmpty()) return -1;
fuel += pq.poll();
stops++;
}
return stops;
}
}#include <vector>
#include <queue>
using namespace std;
int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
priority_queue<int> pq;
int i = 0, n = stations.size(), stops = 0;
int fuel = startFuel;
while (fuel < target) {
while (i < n && stations[i][0] <= fuel)
pq.push(stations[i++][1]);
if (pq.empty()) return -1;
fuel += pq.top(); pq.pop();
stops++;
}
return stops;
}var minRefuelStops = function(target, startFuel, stations) {
const maxHeap = [];
let stops = 0, fuel = startFuel, i = 0, n = stations.length;
function push(value) {
let pos = maxHeap.length;
maxHeap.push(value);
while (pos > 0) {
let parent = (pos - 1) >> 1;
if (maxHeap[parent] >= maxHeap[pos]) break;
[maxHeap[parent], maxHeap[pos]] = [maxHeap[pos], maxHeap[parent]];
pos = parent;
}
}
function pop() {
const max = maxHeap[0];
const last = maxHeap.pop();
if (maxHeap.length > 0) {
maxHeap[0] = last;
let pos = 0;
while (true) {
let left = 2 * pos + 1;
let right = 2 * pos + 2;
let largest = pos;
if (left < maxHeap.length && maxHeap[left] > maxHeap[largest]) largest = left;
if (right < maxHeap.length && maxHeap[right] > maxHeap[largest]) largest = right;
if (largest === pos) break;
[maxHeap[pos], maxHeap[largest]] = [maxHeap[largest], maxHeap[pos]];
pos = largest;
}
}
return max;
}
while (fuel < target) {
while (i < n && stations[i][0] <= fuel)
push(stations[i++][1]);
if (maxHeap.length === 0) return -1;
fuel += pop();
stops++;
}
return stops;
};#include <stdio.h>
#include <stdlib.h>
int minRefuelStops(int target, int startFuel, int** stations, int stationsSize){
int i = 0, fuel = startFuel, stops = 0;
int *pq = (int*)malloc((stationsSize + 1) * sizeof(int));
int pqSize = 0;
while (fuel < target) {
while (i < stationsSize && stations[i][0] <= fuel) {
int j = pqSize++;
while (j > 0 && pq[j - 1] < stations[i][1]) {
pq[j] = pq[j - 1];
j--;
}
pq[j] = stations[i][1];
i++;
}
if (pqSize == 0) return -1;
fuel += pq[--pqSize];
stops++;
}
free(pq);
return stops;
}using System;
using System.Collections.Generic;
public class Solution {
public int MinRefuelStops(int target, int startFuel, int[][] stations) {
var pq = new SortedSet<(int, int)>();
int fuel = startFuel, i = 0, stops = 0;
while (fuel < target) {
while (i < stations.Length && stations[i][0] <= fuel) {
pq.Add((-stations[i][1], i));
i++;
}
if (pq.Count == 0) return -1;
fuel += -pq.Max.Item1;
pq.Remove(pq.Max);
stops++;
}
return stops;
}
}Using Python's heapq, we mimic a max heap by adding negative fuel values to the min heap, allowing us to efficiently manage fuel amounts. Unlike a typical max heap, the smallest (most negative, hence largest positive fuel) is at the heap's front.
Time Complexity: O(n log n), from heap operations with all stations.
Space Complexity: O(n), dictated by heap storage of fuel amounts.
Approach 2: Dynamic Programming Approach
In this approach, we use dynamic programming to track the maximum distance reached with a given number of refuel stops. By simulating the range expansions step-by-step at each station, we keep updating our maximum reach for each refuel stop count.
This works by creating an array dp where dp[i] stands for the farthest distance we can reach with i stops. Initially, dp[0] is initialized with startFuel, and the rest are kept at zero. As we iterate through the stations, we update this dp array backwards so as not to overwrite data prematurely. For each station, we update the dp array to reflect the best possible distance for each number of stops, which includes potentially refueling at that station.
def minRefuelStops(target, startFuel, stations):
dp = [0] * (len(stations) + 1)
dp[0] = startFuel
for i, (position, fuel) in enumerate(stations):
for t in range(i, -1, -1):
if dp[t] >= position:
dp[t + 1] = max(dp[t + 1], dp[t] + fuel)
for i, d in enumerate(dp):
if d >= target:
return i
return -1class Solution {
public int minRefuelStops(int target, int startFuel, int[][] stations) {
long[] dp = new long[stations.length + 1];
dp[0] = startFuel;
for (int i = 0; i < stations.length; ++i) {
for (int t = i; t >= 0; --t) {
if (dp[t] >= stations[i][0])
dp[t + 1] = Math.max(dp[t + 1], dp[t] + stations[i][1]);
}
}
for (int i = 0; i <= stations.length; ++i) {
if (dp[i] >= target) return i;
}
return -1;
}
}#include <vector>
#include <algorithm>
using namespace std;
int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
vector<long> dp(stations.size() + 1, 0);
dp[0] = startFuel;
for (int i = 0; i < stations.size(); ++i) {
for (int t = i; t >= 0; --t) {
if (dp[t] >= stations[i][0])
dp[t + 1] = max(dp[t + 1], dp[t] + stations[i][1]);
}
}
for (int i = 0; i <= stations.size(); ++i) {
if (dp[i] >= target) return i;
}
return -1;
}var minRefuelStops = function(target, startFuel, stations) {
const dp = new Array(stations.length + 1).fill(0);
dp[0] = startFuel;
for (let i = 0; i < stations.length; i++) {
for (let t = i; t >= 0; t--) {
if (dp[t] >= stations[i][0])
dp[t + 1] = Math.max(dp[t + 1], dp[t] + stations[i][1]);
}
}
for (let i = 0; i <= stations.length; i++) {
if (dp[i] >= target)
return i;
}
return -1;
};#include <string.h>
int minRefuelStops(int target, int startFuel, int** stations, int stationsSize) {
long dp[stationsSize + 1];
memset(dp, 0, sizeof(dp));
dp[0] = startFuel;
for (int i = 0; i < stationsSize; i++) {
for (int t = i; t >= 0; t--) {
if (dp[t] >= stations[i][0])
dp[t + 1] = fmax(dp[t + 1], dp[t] + stations[i][1]);
}
}
for (int i = 0; i <= stationsSize; i++) {
if (dp[i] >= target) return i;
}
return -1;
}public class Solution {
public int MinRefuelStops(int target, int startFuel, int[][] stations) {
long[] dp = new long[stations.Length + 1];
dp[0] = startFuel;
for (int i = 0; i < stations.Length; ++i) {
for (int t = i; t >= 0; --t) {
if (dp[t] >= stations[i][0])
dp[t + 1] = Math.Max(dp[t + 1], dp[t] + stations[i][1]);
}
}
for (int i = 0; i <= stations.Length; ++i) {
if (dp[i] >= target) return i;
}
return -1;
}
}The Python solution with a dp array, indicates maximum potential reach with each series of refuels analyzed at stations. Duplicity checking and improvements on distance-by-distance basis ensures ratios and possibilities are efficiently managed.
Time Complexity: O(n^2), concentrated on iteration plus nested handling of all discovered lengths, relative to positions.
Space Complexity: O(n), forming a dp vector aligned straightforward with fuel assessments per station presence.
Approach 3: Greedy + Priority Queue (Max-Heap)
We can use a priority queue (max-heap) pq to record the fuel amounts of all the gas stations we have passed. Each time the fuel is insufficient, we greedily take out the maximum fuel amount, which is the top element of pq, and accumulate the number of refuels ans. If pq is empty and the current fuel is still insufficient, it means we cannot reach the destination, and we return -1.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n represents the number of gas stations.
function minRefuelStops(target: number, startFuel: number, stations: number[][]): number {
const pq = new MaxPriorityQueue<number>();
let [ans, pre] = [0, 0];
stations.push([target, 0]);
for (const [pos, fuel] of stations) {
const dist = pos - pre;
startFuel -= dist;
while (startFuel < 0 && !pq.isEmpty()) {
startFuel += pq.dequeue();
ans++;
}
if (startFuel < 0) {
return -1;
}
pq.enqueue(fuel);
pre = pos;
}
return ans;
}func minRefuelStops(target int, startFuel int, stations [][]int) int {
pq := &hp{}
ans, pre := 0, 0
stations = append(stations, []int{target, 0})
for _, station := range stations {
pos, fuel := station[0], station[1]
dist := pos - pre
startFuel -= dist
for startFuel < 0 && pq.Len() > 0 {
startFuel += heap.Pop(pq).(int)
ans++
}
if startFuel < 0 {
return -1
}
heap.Push(pq, fuel)
pre = pos
}
return ans
}
type hp struct{ sort.IntSlice }
func (h hp) Less(i, j int) bool { return h.IntSlice[i] > h.IntSlice[j] }
func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
a := h.IntSlice
v := a[len(a)-1]
h.IntSlice = a[:len(a)-1]
return v
}use std::collections::BinaryHeap;
impl Solution {
pub fn min_refuel_stops(target: i32, mut start_fuel: i32, mut stations: Vec<Vec<i32>>) -> i32 {
let mut pq = BinaryHeap::new();
let mut ans = 0;
let mut pre = 0;
stations.push(vec![target, 0]);
for station in stations {
let pos = station[0];
let fuel = station[1];
let dist = pos - pre;
start_fuel -= dist;
while start_fuel < 0 && !pq.is_empty() {
start_fuel += pq.pop().unwrap();
ans += 1;
}
if start_fuel < 0 {
return -1;
}
pq.push(fuel);
pre = pos;
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach using Max Heap | Time Complexity: O(n log n), from heap operations with all stations. Space Complexity: O(n), dictated by heap storage of fuel amounts. |
| Dynamic Programming Approach | Time Complexity: O(n^2), concentrated on iteration plus nested handling of all discovered lengths, relative to positions. Space Complexity: O(n), forming a dp vector aligned straightforward with fuel assessments per station presence. |
| Greedy + Priority Queue (Max-Heap) | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming | O(n^2) | O(n) | When explaining state transitions or building intuition about how refueling choices affect reachable distance |
| Greedy with Max Heap | O(n log n) | O(n) | Best general solution for interviews and large inputs; efficiently selects the largest previous fuel station |
Frequently asked questions
Is Minimum Number of Refueling Stops easy or hard?
Minimum Number of Refueling Stops is classified as a Hard problem because the optimal solution requires recognizing a greedy pattern combined with a priority queue. Many developers initially attempt dynamic programming before discovering the more efficient heap-based approach.
Minimum Number of Refueling Stops Python/Java solution
Most implementations use a priority queue to store fuel from reachable stations. In Python, a heap (often simulated as a max heap using negative values) is used. In Java or C++, a PriorityQueue or priority_queue provides efficient O(log n) insertion and removal for the greedy algorithm.
How to solve Minimum Number of Refueling Stops in O(n log n)?
Iterate through stations while tracking the maximum distance reachable with your current fuel. Add fuel amounts of reachable stations to a max heap. When you cannot move forward, pop the largest fuel value from the heap and refuel. Each heap pop counts as a stop, leading to an O(n log n) algorithm.
What is the best approach for Minimum Number of Refueling Stops?
The optimal approach uses a greedy strategy with a max heap (priority queue). As you pass stations, push their fuel amounts into the heap. Whenever your fuel is insufficient to continue, refuel using the largest available station from the heap. This ensures the fewest stops while running in O(n log n) time and O(n) space.
Is Minimum Number of Refueling Stops asked at Google/Amazon/Meta?
Minimum Number of Refueling Stops is a classic greedy and heap interview problem that has appeared in interviews at large tech companies including Google, Amazon, and Meta. It tests your ability to combine greedy decision making with a priority queue data structure.
What data structure is used in Minimum Number of Refueling Stops?
A max heap (priority queue) is the key data structure in the optimal solution. It stores fuel amounts from stations you have already passed, allowing you to quickly choose the largest available refuel option when your fuel becomes insufficient.
What is the time complexity of Minimum Number of Refueling Stops?
The greedy max heap solution runs in O(n log n) time because each station may be pushed and popped from the heap once. The dynamic programming alternative runs in O(n^2) time with O(n) space since it updates reachable distances for each possible number of stops.