Sponsored
Sponsored
This approach leverages a greedy strategy with a max heap to ensure that whenever we're out of fuel, we choose to refuel from the station that offers the most fuel, maximizing our reach.
We traverse through the list of stations, when we reach a station, we check if we need to refuel (i.e., if our current fuel can't get us to the next station). If so, we refuel from the stations we've passed (choosing the one with the most fuel available). We keep track of the number of stops and return that as our result once we reach the target, or return -1 if it's not possible to reach the target.
Time Complexity: O(n log n), as each insertion into the heap takes O(log n), and we perform this operation n times.
Space Complexity: O(n), storing the maximum fuel to be reused in a max-heap equivalent array.
1from heapq import heappush, heappop
2
3def minRefuelStops(target, startFuel, stations):
4 heap = []
5 i, stops, fuel = 0
Using Python's heapq, we mimic a max heap by adding negative fuel values to the min heap, allowing us to efficiently manage fuel amounts. Unlike a typical max heap, the smallest (most negative, hence largest positive fuel) is at the heap's front.
In this approach, we use dynamic programming to track the maximum distance reached with a given number of refuel stops. By simulating the range expansions step-by-step at each station, we keep updating our maximum reach for each refuel stop count.
This works by creating an array dp where dp[i] stands for the farthest distance we can reach with i stops. Initially, dp[0] is initialized with startFuel, and the rest are kept at zero. As we iterate through the stations, we update this dp array backwards so as not to overwrite data prematurely. For each station, we update the dp array to reflect the best possible distance for each number of stops, which includes potentially refueling at that station.
Time Complexity: O(n^2), as each station iterates over previous positions in potentially worst-case scenarios.
Space Complexity: O(n), where n is the station count and the dp array stores potential distances.
1#include <string.h>
2
3int minRefuelStops(int target, int startFuel, int** stations, int stationsSize) {
4 long dp[stationsSize + 1];
5 memset(dp, 0, sizeof(dp));
6 dp[0] = startFuel;
7
8 for (int i = 0; i < stationsSize; i++) {
9 for (int t = i; t >= 0; t--) {
10 if (dp[t] >= stations[i][0])
11 dp[t + 1] = fmax(dp[t + 1], dp[t] + stations[i][1]);
12 }
13 }
14
15 for (int i = 0; i <= stationsSize; i++) {
16 if (dp[i] >= target) return i;
17 }
18 return -1;
19}
20This solution makes use of a dynamic programming array to update our fuel positions iteratively for each station. The backwards iteration allows evaluating each possibility of reaching a station, managing cumulative refueling statuses effectively and efficiently.