Minimum Number Of Refueling Stops - Leetcode Solution

The problem "Minimum Number Of Refueling Stops" on LeetCode asks us to find the minimum number of refueling stops required to reach the destination while traveling from the starting point with limited fuel capacity and given fuel stations along the way.

Here's a detailed solution to the problem:

Approach: We can solve this problem by using the Greedy algorithm. The basic idea is to always refuel at the farthest possible distance and keep track of the number of refueling stops made. At each step, we will refuel at the station with the maximum fuel capacity that we can reach. If we cannot reach any station, then we cannot reach the destination and we return -1. We keep adding the number of stops made at each station and return the total at the end.

Algorithm:

1. Initialize the variables:

• distance: The current distance covered from the starting point.
• stops: The current number of fuel stops made.
• fuel: The current fuel capacity.

2. For each station (until the end of the destination is reached):

• If we cannot reach the next station, refill at the farthest station we can reach.
• If we cannot reach any station, return -1 as it's impossible to reach the destination.
• If we can reach the next station, don't refuel and move on to the next station.

3. Return the total number of refueling stops made.

Code:

class Solution { public: int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {

    int distance = startFuel; // Distance covered so far.
    int stops = 0; // Number of stops made so far.
    int fuel = startFuel; // Fuel remaining after covering the current distance.
    
    // Create a priority queue to store the stations according to the fuel they provide.
    priority_queue<int> pq; 
    
    for (int i = 0; i < stations.size(); i++) {
        
        // If the fuel in the tank is less than the distance to the next station.
        while (fuel < stations[i][0] - distance) {
            
            if (pq.empty()) return -1; // Cannot reach any station so return -1.
            
            fuel += pq.top(); // Refuel at the farthest possible station.
            pq.pop(); // Remove the fuel station from the priority queue.
            stops++; // Count the number of refueling stops made.
            
        }
        
        // Push the remaining fuel after covering the distance from the current station.
        pq.push(stations[i][1]);
        fuel -= stations[i][0] - distance;
        distance = stations[i][0];
        
    }
    
    // If there is not enough fuel to reach the destination.
    while (fuel < target - distance) {
        
        if (pq.empty()) return -1; // Cannot reach the destination so return -1.
        
        fuel += pq.top();
        pq.pop();
        stops++;
        
    }
    
    return stops;
}

};

Time Complexity: The time complexity of the algorithm is O(nlogn). We have to process all the stations, so the time complexity involved in processing all the stations is O(n). However, we are using a priority queue to keep track of the available fuel sources, and the total time is O(nlogn) because the time required to add and remove elements from the priority queue is log(n).

Space Complexity: The space complexity of the algorithm is O(n) because we are using a priority queue to store the stations. The priority queue can have a maximum of n elements, so the space required is O(n). In addition to this, we are using a few extra variables to store the current fuel and distance which are constant space, so the total space complexity is O(n).

1