871. Minimum Number of Refueling Stops

HardGreedyArrayDynamic ProgrammingHeap (Priority Queue)

Problem Description

This problem involves simulating a car's journey from a starting position to a destination, which is a certain number of miles away (target). The journey is not direct, as there are gas stations along the way, each with a certain amount of fuel available. The car starts with a certain amount of fuel (startFuel), and the goal is to determine the minimum number of stops at gas stations required to reach the destination. If the car can't reach the destination, the function should return -1. Importantly, the car consumes fuel at a rate of one liter per mile.

The gas stations are defined in an array called stations, where stations[i] contains two elements: the position of the station relative to the starting point, and the amount of fuel available at that station (fuel[i]). The car can refuel whenever it reaches a gas station and can take all the gas from that station. The problem's constraints allow the car to reach a gas station or the destination with exactly 0 fuel left and still be able to refuel or be considered arrived, respectively.

Intuition

The problem can be approached as a greedy algorithm combined with a priority queue. The intuition is to drive from one station to the next, using up fuel, and to always have enough fuel to reach the next station or the destination. However, since the car needs to minimize the number of stops, it shouldn't stop at every station to refuel. Instead, the car should only stop when it is necessary—meaning when it's running out of fuel.

To implement this strategy, use a max-heap (priority queue), where you can store the amount of fuel from stations the car has passed without stopping. If the car runs out of fuel before reaching the next station or the destination, it should refuel by taking the most significant amount of fuel it has passed. This is why using a max-heap is useful; it allows for accessing the largest amount of fuel quickly. The steps are as follows:

Add each station's fuel to the priority queue when passing by without refueling.
If the car needs to refuel (fuel drops below 0), it takes the largest available fuel from the priority queue, and that counts as a stop.
If the car runs out of both fuel and potential refuels in the priority queue, it's impossible to reach the destination, and the function should return -1.
Continue this process until the destination is reached.
The number of times fuel is taken from the priority queue represents the minimum number of refueling stops required.

The consideration of necessary pauses for refueling ensures the optimal number of stops. By initializing the stations array with the target position (and zero fuel), the loop also conveniently handles the case of reaching the destination.

Learn more about Greedy, Dynamic Programming and Heap (Priority Queue) patterns.

Solution Approach

The solution uses a priority queue to keep track of the gas amounts available at stations we've passed and a greedy algorithm approach to minimize the number of stops. Here's a step-by-step explanation of how the provided Python code implements this solution:

Initialize priority queue and variables: The q variable represents the priority queue (a max-heap), which is used to store the fuel amounts of gas stations that the car has passed. The prev variable stores the position of the last gas station, or the starting point initially, and ans is the count of refueling stops.
Add the destination as a station: To handle the arrival at the destination, it adds the destination itself as a gas station into the stations list with 0 fuel.
Loop through stations: For each gas station in the stations list, calculate the distance d from the prev position to this station's position a. Subtract this distance from the startFuel to simulate driving to the station.
Refuel if necessary: If startFuel drops below 0, it means the car needs to refuel. It repeatedly pops the largest amount of fuel from the priority queue (note: Python's heapq module provides a min-heap, so we store negative values to simulate a max-heap). After each pop, increment the ans counter. Keep refueling (popping from the queue) until startFuel is non-negative (indicating the car can reach the next station or the destination).
Check if destination is reachable: After attempting to refuel from the priority queue, if startFuel is still negative, it means the car cannot reach the next station or the destination, and the function returns -1.
Push current station's fuel into the queue: Regardless of whether the car needed to refuel to reach the current station, push the negative of the current station's fuel amount b into the priority queue (in this way, we are preparing for a potential future refuel stop).
Update prev position: Update the prev variable to the current station's position for the next iteration.
Return the number of stops: After the loop completes (which happens when the car reaches the 'fake' gas station at the destination), return ans as the total number of refueling stops made.

The algorithm effectively determines the minimal number of refueling stops by always picking the refuel options that gave the maximum range expansion when necessary. This approach ensures that each stop contributes as much as possible towards progressing to the destination, thereby minimizing the total number of stops needed.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example to illustrate the solution approach.

Given:

target distance to reach: 10 miles
startFuel: 3 liters
stations: [[3, 3], [7, 2]], where the first element in each pair is the position of the station, and the second element is the fuel available at that station.

Approach:

Here is a step-by-step walkthrough applying the solution steps from the content above.

Initialize priority queue and variables: q = [] (this is the max-heap for storing gas station fuel amounts), prev = 0 (start position), and ans = 0 (no refuel stops yet).
Add the destination as a station: Update stations to [[3, 3], [7, 2], [10, 0]] to include the target as a station with 0 fuel.
Loop through the stations: Starting at first station:
- Station at 3 miles offering 3 liters of fuel.
- Distance d from prev (0) to this station's position (3) is 3.
- startFuel becomes 3 - 3 = 0. The car arrives at the station with no fuel left.
Refuel if necessary: Since startFuel is 0, there's no need to refuel yet (no past stations to get fuel from).
Push current station's fuel into the queue: Push -3 into priority queue q.
Update prev position: prev becomes 3.

Continuing to the next station:
- Station at 7 miles offering 2 liters of fuel.
- Distance d from prev (3) to this station's position (7) is 4.
- startFuel before arriving at this station is 0, and after subtracting the distance it becomes -4, which means the car needs to refuel.
Refuel if necessary: Pop the largest amount of fuel from q, which is -3 (representing 3 liters of fuel we passed earlier).
- startFuel becomes -4 + 3 = -1. One stop has been made, so increment ans to 1.
- Since startFuel is still negative, we would need to stop if we had any more fuel in q, but since there's no more fuel in the queue, we continue.
Push current station's fuel into the queue: Push -2 into priority queue q.
Update prev position: prev becomes 7.

Arriving at the destination (fake station at 10 miles):
- Distance from prev (7) to destination (10) is 3.
- startFuel becomes -1 - 3 = -4, which requires another refuel.
Refuel if necessary: Pop the largest amount of fuel from q, which is now -2 (representing 2 liters).
- startFuel becomes -4 + 2 = -2. Another stop is made, increment ans to 2.
- startFuel is still negative, pop the last from q. However, there is no fuel left, meaning the car cannot reach the destination.
Check if destination is reachable: When attempting to refuel from an empty queue, the function should return -1 as the car cannot reach the destination.

However, note that the example chose a scenario where we cannot reach the destination given the stations and starting fuel. If the stations provided more fuel or were positioned differently, the car could have reached the destination, and ans would represent the minimal number of stops needed to reach the target.

Solution Implementation

1from heapq import heappush, heappop
2from typing import List
3
4class Solution:
5    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
6        # Max-heap to store available fuel at stations we have passed
7        fuel_maxheap = []
8      
9        # The position of the last station we processed
10        previous_station_position = 0
11      
12        # The number of refueling stops we have made
13        refuel_stops = 0
14
15        # Add the target as a station to make sure we process the journey's end
16        stations.append([target, 0])
17      
18        # Process each station on the route
19        for position, fuel in stations:
20            # Distance to the next station (or target)
21            distance = position - previous_station_position
22            startFuel -= distance  # Subtract the distance from the current fuel
23          
24            # Check if we need to refuel from passed stations (must take fuel from the station with the most fuel)
25            while startFuel < 0 and fuel_maxheap:
26                startFuel += -heappop(fuel_maxheap)  # Get fuel from the heap (invert the negative value)
27                refuel_stops += 1  # Increment the refuel counter
28          
29            # If we cannot reach the next station/target and there is no more fuel in the heap, return -1
30            if startFuel < 0:
31                return -1
32          
33            # If the station offers fuel, add it to the heap (store as negative for max-heap)
34            heappush(fuel_maxheap, -fuel)
35          
36            # Update the previous station position
37            previous_station_position = position
38      
39        # Return the number of refueling stops after processing all stations
40        return refuel_stops
41

1class Solution {
2    public int minRefuelStops(int target, int startFuel, int[][] stations) {
3        // Max heap to store available fuel amounts at the stations we've passed
4        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
5        int numStations = stations.length; // Total number of fuel stations
6        int prevPosition = 0; // The previous position after the last fuel stop
7        int numRefuels = 0; // The number of refueling stops made
8
9        // Loop through all stations, adding a 'virtual' station at the target
10        // to calculate the fuel needed to reach the target
11        for (int i = 0; i <= numStations; i++) {
12            // Distance from the previous station or from the start if it's the first station
13            int distance = (i < numStations ? stations[i][0] : target) - prevPosition;
14            // Subtract the distance from the current fuel
15            startFuel -= distance;
16            // Use fuel from the max heap (previously visited stations) if we are out of fuel
17            while (startFuel < 0 && !maxHeap.isEmpty()) {
18                // Refuel using the station with the most fuel we've passed
19                startFuel += maxHeap.poll();
20                numRefuels++; // Increment the refuel count
21            }
22            // If we can't refuel and the current fuel is less than zero, we can't reach the target
23            if (startFuel < 0) {
24                return -1;
25            }
26            // If it's not a virtual station, add the fuel from this station to the max heap
27            if (i < numStations) {
28                maxHeap.offer(stations[i][1]);
29                // Update previous position to the current station's position
30                prevPosition = stations[i][0];
31            }
32        }
33        // Return the minimum number of refueling stops made to reach the target
34        return numRefuels;
35    }
36}
37

1#include <vector>
2#include <queue>
3using namespace std;
4
5class Solution {
6public:
7    // Method to find the minimum number of refueling stops required
8    int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
9        // Max heap to store the fuel available at the stations
10        priority_queue<int> fuelMaxHeap; 
11      
12        // Add a final station at the target position with 0 fuel
13        stations.push_back({target, 0});
14      
15        // Initialize answer (minimum refueling stops) and previous station
16        int minStops = 0, prevStationDist = 0;
17      
18        // Iterate through the stations along the route
19        for (auto& station : stations) {
20            // Calculate the distance to the current station from the previous station
21            int distance = station[0] - prevStationDist;
22          
23            // Reduce the start fuel by the distance traveled
24            startFuel -= distance;
25          
26            // While the fuel is not enough to reach the next station and there's fuel in the max heap, refuel
27            while (startFuel < 0 && !fuelMaxHeap.empty()) {
28                // Add the max fuel available from passed stations
29                startFuel += fuelMaxHeap.top();
30                fuelMaxHeap.pop();
31              
32                // Increment the minimum stops as we've refueled
33                ++minStops;
34            }
35          
36            // If the fuel is still not enough, return -1 indicating it is not possible
37            if (startFuel < 0) {
38                return -1;
39            }
40          
41            // Add the current station's fuel to the max heap
42            fuelMaxHeap.push(station[1]);
43          
44            // Update the previous station distance
45            prevStationDist = station[0];
46        }
47      
48        // Return the minimum number of stops to refuel
49        return minStops;
50    }
51};
52

1// Importing array type for vectors.
2import { PriorityQueue } from './PriorityQueue'; // Assuming a PriorityQueue implementation available
3
4// Function to find the minimum number of refueling stops required.
5// Takes the target distance, starting fuel level, and an array of fuel stations.
6function minRefuelStops(target: number, startFuel: number, stations: number[][]): number {
7    // Priority Queue (Max Heap) to store the fuel available at the stations.
8    let fuelMaxHeap = new PriorityQueue<number>((a, b) => b - a);
9  
10    // Add a final station at the target position with 0 fuel.
11    stations.push([target, 0]);
12  
13    // Initialize answer (minimum refueling stops) and previous station distance.
14    let minStops = 0, prevStationDist = 0;
15  
16    // Iterate through the stations along the route.
17    for (let station of stations) {
18        // Calculate the distance to the current station from the previous station.
19        let distance = station[0] - prevStationDist;
20      
21        // Reduce the start fuel by the distance traveled.
22        startFuel -= distance;
23      
24        // While the fuel is not enough to reach the next station and there's fuel in the max heap, refuel.
25        while (startFuel < 0 && !fuelMaxHeap.isEmpty()) {
26            // Add the max fuel available from passed stations.
27            startFuel += fuelMaxHeap.dequeue();
28          
29            // Increment the minimum stops as we've refueled.
30            minStops += 1;
31        }
32      
33        // If the fuel is still not enough, return -1 indicating it is not possible to reach the target.
34        if (startFuel < 0) {
35            return -1;
36        }
37      
38        // Add the current station's fuel to the max heap.
39        fuelMaxHeap.enqueue(station[1]);
40      
41        // Update the previous station distance.
42        prevStationDist = station[0];
43    }
44  
45    // Return the minimum number of stops to refuel.
46    return minStops;
47}
48

Time and Space Complexity

Time Complexity

The given code snippet involves iterating through the list of fuel stations once, which means the time complexity is at least O(N) where N is the number of fuel stations. However, since there are heap operations within the loop (specifically heappop and heappush), we have to consider their impact as well.

The worst-case time complexity for both heappush and heappop is O(log M), where M is the number of elements in the heap. In the worst-case scenario, every station could potentially be added to the heap, so M can be at most N.

Since a heappop operation could potentially occur for each station in the list (thus iterating through the list N times), the worst-case time complexity becomes O(N * log N).

To sum up, the total time complexity of the function is O(N * log N).

Space Complexity

The space complexity of the function is primarily due to the usage of the priority queue (q). In the worst case, the priority queue could contain an entry for every station if no refueling was needed until the end, thus containing N elements. Hence, the space complexity is O(N) because that's the maximum amount of space that the priority queue will use. No other data structures in the solution use a significant amount of memory proportional to the input size, so they do not influence the space complexity beyond O(N).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don't know