## DEV Community is a community of 892,765 amazing developers

We're a place where coders share, stay up-to-date and grow their careers. # 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.

#### Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

A car travels from a starting position to a destination which is `target` miles east of the starting position.

Along the way, there are gas stations. Each `station[i]` represents a gas station that is `station[i]` miles east of the starting position, and has `station[i]` liters of gas.

The car starts with an infinite tank of gas, which initially has `startFuel` liters of fuel in it. It uses `1` liter of gas per `1` 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.

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 `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.

#### Examples:

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

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, stations[i] <= 10^9`
• `0 <= stations.length <= 500`
• `0 < stations < stations < ... < stations[stations.length-1] < target`

#### Idea:

(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

#### Implementation:

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.

#### Javascript Code:

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]
while (F < dist) {
if (!pq.size()) return -1
F += pq.dequeue().element, ans++
}
if (i < n) pq.enqueue(S[i])
}
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, left, right, temp,
i = 1, child = heap > heap ? 3 : 2
if (heap.length > 2) heap = 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
}
}

for (let i = 0; i <= n; i++) {
let dist = i === n ? T : S[i]
while (F < dist) {
if (heap.length === 1) return -1
F += hpop(), ans++
}
if (i < n) hpush(S[i])
}
return ans
};
``````

#### Python Code:

``````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]
while F < dist:
if len(heap) == 0: return -1
F -= heappop(heap)
ans += 1
if i < n: heappush(heap, -S[i])
return ans
``````

#### Java Code:

``````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];
while (F < dist) {
if (pq.size() == 0) return -1;
F += pq.poll();
ans++;
}
}
return ans;
}
}
``````

#### C++ Code:

``````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];
while (F < dist) {
if (!pq.size()) return -1;
F += pq.top(), ans++;
pq.pop();
}
if (i < n) pq.push(S[i]);
}
return ans;
}
};
``````