Leetcode 871. Minimum Number of Refueling Stops

Problem Explanation:

This problem seems a bit complicated due to its requirements. The situation is that a car wants to reach at a specific destination which is east of its starting point. There are various gas stations on the way, each with its own gas capacity, which can help the car reach its destination. The car starts with an infinite tank and some initial fuel. The car uses 1 liter of gas per mile it drives. The car may stop on the way to refuel. We have to find the least time the car has to stop for the refuel. If the car cannot reach the destination, we should return -1. Remember, even if the car reaches the gas station or its destination with 0 fuel left, it can still take fuel and be considered to have arrived.

For example, if the destination is 100 miles, starting fuel is 10 liters and there are gas stations at 10, 20, 30 and 60 providing 60, 30, 30, 40 liters of fuel respectively, the car can arrive its destination with 2 stops as follows: First stop at position 10 consuming 10 liters of fuel and refuel 60 liters of gas, then move to position 60 consuming 50 liters of fuel and refuel 40 liters of gas, finally reaching the target.

Solution Approach:

Dynamic Programming is suitable for this problem. The idea is to maintain a dp array where dp[i] stores the furthest distance that can be reached with i refuels. When we encounter a gas station, we can choose to refuel there or not, so for each gas station, we try to update dp array backwards. When we reach the end, we check dp array to find out the minimum refuels that can reach the target.

Solution in Python:

1
2python
3import heapq
4
5class Solution:
6    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
7        pq = []
8        stations.append([target, float('inf')])
9
10        ans = pre = 0
11        tank = startFuel
12        for loc, cap in stations:
13            tank -= loc - pre
14            while pq and tank < 0: # must refuel in past
15                tank += -heapq.heappop(pq)
16                ans += 1
17            if tank < 0: return -1
18            heapq.heappush(pq, -cap)
19            pre = loc
20
21        return ans

Solution in Java

1
2java
3class Solution {
4    public int minRefuelStops(int target, int startFuel, int[][] stations) {
5        int i = 0, res;
6        PriorityQueue<Integer> pq = new PriorityQueue(Collections.reverseOrder());
7        for (res = 0; startFuel < target; res++) {
8            while (i < stations.length && stations[i][0] <= startFuel)
9                pq.add(stations[i++][1]);
10            if (pq.isEmpty()) return -1;
11            startFuel += pq.poll();
12        }
13        return res;
14    }
15}

Solution in JavaScript

1
2javascript
3var minRefuelStops = function(target, startFuel, stations) {
4    let fuel = startFuel, stops = 0, i = 0, pq = [];
5    while(true) {
6        while(i < stations.length && stations[i][0] <= fuel) { 
7            pq.push(stations[i++][1]);
8        }
9        if(fuel >= target) {
10            return stops;
11        }
12        if(pq.length === 0) {
13            return -1;
14        }
15        fuel += pq.pop();
16        stops++;
17    }
18};

Solution in C++

1
2c++
3class Solution {
4public:
5    int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
6        priority_queue<int> pq;
7        stations.push_back({target, 0});
8        int ans = 0, prev = 0;
9        for (auto& station : stations) {
10            startFuel -= station[0] - prev;
11            while (!pq.empty() && startFuel < 0) {
12                startFuel += pq.top();
13                pq.pop();
14                ans += 1;
15            }
16            if (startFuel < 0) return -1;
17            pq.push(station[1]);
18            prev = station[0];
19        }
20        return ans;
21    }
22};

Solution in C#

1
2csharp
3public class Solution {
4    public int MinRefuelStops(int target, int startFuel, int[][] stations) {
5        int n = stations.Length, res = 0;
6        long[] dp = new long[n + 1];
7        dp[0] = startFuel;
8        for (int i = 0; i < n; ++i)
9            for (int t = i; t >= 0 && dp[t] >= stations[i][0]; --t)
10                dp[t + 1] = Math.Max(dp[t + 1], dp[t] + stations[i][1]);
11        for (; res <= n && dp[res] < target; ++res) ;
12        return res <= n ? res : -1;
13    }
14}

In the solutions given above, if the gas in the tank is less than our next destination, we should refuel in the past. We use a priority queue pq to maintain the refueled gas in the past. We refuel the station with more fuel. If we cannot refuel, we return -1, otherwise we finally return the minimum refueling stops res.The priority queue will ensure that at each point we are refueling, we are adding the station with the maximum amount of fuel to our total fuel capacity. Thus, the greedy algorithm of always choosing the maximum benefit at each stage leads us to the minimum total number of stops.

This greedy approach works because refueling at a station with more gas allows us to cover maximum distance, thus reducing the possibility of having to make an extra stop. This is as opposed to refueling at a station with less gas, which may give us immediate benefit but can lead to an extra stop in the future.

This problem tests your understanding of dynamic programming, greedy algorithms and Priority Queue data structure. Understanding how to build up to a solution by considering all possibilities and then pruning away inefficient ones is key to cracking problems like these in professional interviews or coding assessments.

The time complexity for this problem is O(nlogn) due to a sort operation and the use of a priority queue, and the space complexity is O(n) due to extra space required for the priority queue. Here, n is the total number of fuel stations. Thus, the algorithm is very efficient.

It can be further improved for some edge cases. For example, if the destination or any of the stations are beyond the maximum distance that can be reached, these can be pruned right at the beginning. This will save some unnecessary computation and hence optimise the solution slightly. However, the time complexity will remain the same.

In conclusion, solving such problems need combination of intuition for the greedy/dynamic approach, understanding of the problem constraints and mastery over the relevant data structures. Make sure to practice problems from these topics to improve your coding and problem-solving skills.