43
Solution: Minimum Number of Refueling Stops
This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.
(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)
A car travels from a starting position to a destination which is
targetmiles east of the starting position.Along the way, there are gas stations. Each
station[i]represents a gas station that isstation[i][0]miles east of the starting position, and hasstation[i][1]liters of gas.The car starts with an infinite tank of gas, which initially has
startFuelliters of fuel in it. It uses1liter of gas per1mile 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.
What is the least 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
0fuel left, the car can still refuel there. If the car reaches the destination with0fuel 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't 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.
1 <= target, startFuel, stations[i][1] <= 10^90 <= stations.length <= 5000 < stations[0][0] < stations[1][0] < ... < stations[stations.length-1][0] < target
(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)
Since this problem is asking for the least amount of refuelings, we should attempt a greedy approach to the solution. To accomplish that, we should start with 0 refuelings and keep attempting one additional refueling until we find a working solution.
In a naive approach, we would attempt every single combination of 1 refueling station, then every single combination of 2 refueling stations, etc., but that would take way too long.
Instead, let's consider the natural progression of iterating through the list of stations (S). At each station (S[i]) we should first check to see if we have enough fuel to get there.
(Note: Since the station distances are measured in distance from the start, not distance from the last station, it's easier to keep track of the total fuel obtained (F), rather than the unspent fuel, because we can directly compare that to the distance traveled (dist).)
If we didn't have enough fuel to get to the current station, then we should have refueled somewhere. Only a station seen before S[i] is available for this retroactive refueling, however, so we need to choose a prior station at which to have refueled. Given our choice, we should naturally pick the station with the largest reserve of fuel.
Rather than attempting to sort a portion of S each time, we should instead use a max priority queue (or max heap) (pq/heap) to store the previously visited stations' fuel reserves so that we can always choose the ideal station at any point along our iteration.
When we find ourselves unable to reach the next station, we should continue to pull fuel reserves from pq until we have enough. If we run out of reserves while F < dist, then we can never reach the target (T), and should return -1.
We should also keep track of the total number of times (ans) we've removed fuel from the reserves in pq, and iterate one extra time to reach T from the last station. Upon successfully reaching T, we can return ans.
- Time Complexity: O(N log N) where N is the length of S, for up to N insertions and N removals from pq/heap
- Space Complexity: O(N) for pq/heap
Javascript's MaxPriorityQueue() npm is easier to use than, but not as efficient as, a custom max heap implementation. Both are included below for comparison.
Python defaults to a min heap, so we can reverse the signs upon insertion and extraction to achieve an effective max heap implementation.
(Jump to: Problem Description || Solution Idea)
w/ MaxPriorityQueue():
var minRefuelStops = function(T, F, S) {
let n = S.length, pq = new MaxPriorityQueue(), ans = 0
for (let i = 0; i <= n; i++) {
let dist = i === n ? T : S[i][0]
while (F < dist) {
if (!pq.size()) return -1
F += pq.dequeue().element, ans++
}
if (i < n) pq.enqueue(S[i][1])
}
return ans
};w/ custom Max Heap:
var minRefuelStops = function(T, F, S) {
let n = S.length, ans = 0
// custom Max Heap implementation
let heap = [,]
const hpush = val => {
let i = heap.length, par = i >> 1, temp
heap.push(val)
while (heap[par] < heap[i]) {
temp = heap[par], heap[par] = heap[i], heap[i] = temp
i = par, par = i >> 1
}
}
const hpop = () => {
if (heap.length === 1) return null
let top = heap[1], left, right, temp,
i = 1, child = heap[3] > heap[2] ? 3 : 2
if (heap.length > 2) heap[1] = heap.pop()
else heap.pop()
while (heap[i] < heap[child]) {
temp = heap[child], heap[child] = heap[i], heap[i] = temp
i = child, left = i << 1, right = left + 1
child = heap[right] > heap[left] ? right : left
}
return top
}
for (let i = 0; i <= n; i++) {
let dist = i === n ? T : S[i][0]
while (F < dist) {
if (heap.length === 1) return -1
F += hpop(), ans++
}
if (i < n) hpush(S[i][1])
}
return ans
};
(Jump to: Problem Description || Solution Idea)
class Solution:
def minRefuelStops(self, T: int, F: int, S: List[List[int]]) -> int:
n, heap, ans = len(S), [], 0
for i in range(n+1):
dist = T if i == n else S[i][0]
while F < dist:
if len(heap) == 0: return -1
F -= heappop(heap)
ans += 1
if i < n: heappush(heap, -S[i][1])
return ans
(Jump to: Problem Description || Solution Idea)
class Solution {
public int minRefuelStops(int T, int F, int[][] S) {
int n = S.length, ans = 0;
PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> b - a);
for (int i = 0; i <= n; i++) {
int dist = i == n ? T : S[i][0];
while (F < dist) {
if (pq.size() == 0) return -1;
F += pq.poll();
ans++;
}
if (i < n) pq.add(S[i][1]);
}
return ans;
}
}
(Jump to: Problem Description || Solution Idea)
class Solution {
public:
int minRefuelStops(int T, int F, vector<vector<int>>& S) {
int n = S.size(), ans = 0;
priority_queue<int> pq;
for (int i = 0; i <= n; i++) {
int dist = i == n ? T : S[i][0];
while (F < dist) {
if (!pq.size()) return -1;
F += pq.top(), ans++;
pq.pop();
}
if (i < n) pq.push(S[i][1]);
}
return ans;
}
};43