Minimum Number of Refueling Stops
HardPrompt
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
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses dynamic programming to solve the problem. We define dp[i] as the maximum distance one can reach from the starting point by making exactly i refueling stops. Our goal is to find the smallest i for which dp[i] is greater than or equal to the target distance.
Algorithm
- Let
nbe the number of stations. - Create a
longarraydpof sizen + 1.dp[i]will store the maximum distance reachable withistops. - Initialize
dp[0] = startFuel. All otherdpentries are initialized to 0. - Iterate through each station
sfromi = 0ton-1:- For each number of stops
jfromidown to0:- If
dp[j]is greater than or equal to the position of stationi, it means we can reach this station withjstops. - We can potentially refuel here, making it our
(j+1)-th stop. The new maximum reach would bedp[j] + s.fuel. - Update
dp[j+1] = max(dp[j+1], dp[j] + s.fuel).
- If
- For each number of stops
- After iterating through all stations, find the smallest
isuch thatdp[i] >= target. - If no such
iexists, it's impossible to reach the target, so return -1.
Walkthrough
We initialize a dp array of size n+1, where n is the number of gas stations. dp[i] will store the furthest reachable distance with i stops. dp[0] is initialized to startFuel, as this is the maximum distance we can travel without any stops. We then iterate through each gas station s. For each station, we consider the possibility of making it a refueling stop by iterating backwards through the number of stops j. We iterate backwards to ensure that we use each station at most once for a given number of stops. If our current maximum reach with j stops, dp[j], is enough to get to the current station s (i.e., dp[j] >= s.position), we can potentially make this our (j+1)-th stop. By refueling, our new maximum reach with j+1 stops would be dp[j] + s.fuel. We update dp[j+1] to be the maximum of its current value and this new potential reach. After processing all stations, we find the first index i where dp[i] >= target. This i is our answer. If no such i exists, we return -1. We use a long type for the dp array to prevent potential integer overflows with large fuel and target values.
public int minRefuelStops(int target, int startFuel, int[][] stations) { int n = stations.length; long[] dp = new long[n + 1]; dp[0] = startFuel; for (int i = 0; i < n; i++) { int position = stations[i][0]; int fuel = stations[i][1]; for (int j = i; j >= 0; j--) { if (dp[j] >= position) { dp[j + 1] = Math.max(dp[j + 1], dp[j] + fuel); } } } for (int i = 0; i <= n; i++) { if (dp[i] >= target) { return i; } } return -1;}Complexity
Time
O(N^2), where N is the number of stations. We have two nested loops, each iterating up to N.
Space
O(N), where N is the number of stations, to store the `dp` array.
Trade-offs
Pros
The DP state and transition are logical and relatively easy to formulate.
It correctly solves the problem for the given constraints.
Cons
The O(N^2) time complexity is less efficient than the greedy approach, which can be a drawback for larger N.
A more efficient approach is a greedy one. The core idea is to drive as far as possible with the current fuel. When we can no longer proceed, we must refuel. To maximize our travel distance, we should retroactively use the fuel from a station we have already passed that had the largest amount of fuel. A max-heap is the perfect data structure to efficiently find this largest fuel amount among the reachable stations.
Algorithm
- Initialize
stops = 0,currentReach = startFuel, andstationIndex = 0. - Create a max-heap
pqto store fuel from passed stations. - Loop as long as
currentReach < target:- Add the fuel of all stations that are currently reachable (
station.position <= currentReach) to thepq. - If
currentReachis still less thantarget, we must refuel. - If
pqis empty at this point, it's impossible to proceed. Return -1. - Pop the largest fuel amount from
pq, add it tocurrentReach, and incrementstops.
- Add the fuel of all stations that are currently reachable (
- Once
currentReach >= target, the loop terminates. Return the totalstops.
Walkthrough
We simulate the car's journey by keeping track of the maximum distance we can reach, currentReach, which starts at startFuel. We also use a max-heap (implemented as a PriorityQueue in Java) to store the fuel from stations we have passed. We iterate as long as our currentReach is less than the target. In each step of the main loop, we first add all newly reachable stations to our max-heap. A station is reachable if its position is less than or equal to our currentReach. After adding all such stations, we check if we've reached the target. If not, we must refuel. We do this by taking the largest fuel amount from the heap (which corresponds to the best refueling option among the stations we've passed), add it to our currentReach, and increment our stop count. If the heap is empty and we still haven't reached the target, it means we are stranded and cannot proceed, so we return -1. This process continues until we can reach the target, at which point we return the number of stops made.
import java.util.Collections;import java.util.PriorityQueue; public int minRefuelStops(int target, int startFuel, int[][] stations) { if (startFuel >= target) { return 0; } PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); int stops = 0; long currentReach = startFuel; int stationIndex = 0; int n = stations.length; while (currentReach < target) { // Add all reachable stations' fuel to the max-heap while (stationIndex < n && stations[stationIndex][0] <= currentReach) { maxHeap.offer(stations[stationIndex][1]); stationIndex++; } // If we can't reach further and no stations to refuel from, it's impossible if (maxHeap.isEmpty()) { return -1; } // Refuel from the station with the most fuel among those we've passed currentReach += maxHeap.poll(); stops++; } return stops;}Complexity
Time
O(N log N), where N is the number of stations. Each station is pushed onto the heap once (O(log N)) and popped at most once (O(log N)).
Space
O(N), where N is the number of stations, to store the fuel of all stations in the max-heap in the worst case.
Trade-offs
Pros
More efficient time complexity than the DP approach.
The logic of "drive as far as you can, then refuel with the best option" is an elegant and powerful greedy paradigm.
Cons
The correctness of the greedy choice might be less obvious to prove compared to the DP formulation.
Solutions
Solution
class Solution {public int minRefuelStops(int target, int startFuel, int[][] stations) { PriorityQueue<Integer> q = new PriorityQueue<>((a, b)->b - a); int n = stations.length; int prev = 0, ans = 0; for (int i = 0; i < n + 1; ++i) { int d = (i < n ? stations[i][0] : target) - prev; startFuel -= d; while (startFuel < 0 && !q.isEmpty()) { startFuel += q.poll(); ++ans; } if (startFuel < 0) { return -1; } if (i < n) { q.offer(stations[i][1]); prev = stations[i][0]; } } return ans; }}class Solution {public: int minRefuelStops(int target, int startFuel, vector<vector<int>> &stations) { priority_queue<int> q; stations.push_back({target, 0}); int ans = 0, prev = 0; for (auto &s : stations) { int d = s[0] - prev; startFuel -= d; while (startFuel < 0 && !q.empty()) { startFuel += q.top(); q.pop(); ++ans; } if (startFuel < 0) return -1; q.push(s[1]); prev = s[0]; } return ans; }};class Solution: def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int: q = [] prev = ans = 0 stations . append([target, 0]) for a, b in stations: d = a - prev startFuel -= d while startFuel < 0 and q: startFuel -= heappop(q) ans += 1 if startFuel < 0: return - 1 heappush(q, - b) prev = a return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.