Problem statement

https://leetcode.com/problems/minimum-number-of-refueling-stops/

Solution 1

One of the solution use dynamic programming. Let dp[i][j] be a maximum amount of fuel we can have, when we reached station number i and refueled j times before this station (not included). Let us also add two more points to our stops: starting one and ending one. Then, how we can update dp[i][j]: we can

  1. Either refuel on previous station, than we have dp[i-1][j-1] minus distance we covered between i-1 and i stations and plus amount of fuel we get at last station.
  2. Or it can be dp[i-1][j] plus distance we covered between i-1 and i stations.

If we have cand < 0 in our code, than it means we can not reach position i with j refuels, so we leave it equal to minus infinity. Finally, in the end we check last station and find the smallest index where value is not negative and return it.

Complexity

Time complexity is O(n^2), space is O(n^2) as well. Space can be reduced to O(n).

Code

class Solution:
    def minRefuelStops(self, target, startFuel, s):
        s = [[0, startFuel]] + s + [[target, 0]]
        n = len(s)
        t = [(s[i-1][0] - s[i][0], s[i-1][1] + s[i-1][0] - s[i][0]) for i in range(1, n)]
        dp = [[-float("inf")] * n for _ in range(n)]
        dp[0][0] = 0
        
        for i in range(1, n):
            for j in range(1, i+1):
                cand = max(dp[i-1][j] + t[i-1][0], dp[i-1][j-1] + t[i-1][1])
                if cand >= 0: dp[i][j] = cand
        
        for i, elem in enumerate(dp[-1]):
            if elem >= 0: return i - 1
                    
        return -1

Solution 2

There is also O(n log n) complexity solution, using heaps! Let us follow the following strategy: ride until we can, and if we can not, choose the biggest of stations we met previously and refuel at this station. Why it is working? Because in any case we need to spend target amount of fuel, and if we choose station with biggest amount of fuel inside, then we always better if we choose other station. So, the algorithm will work like this:

  1. Add starting and ending position to our stations
  2. Iterate through positions: update fuel: subtract distance we passed
  3. If it happen that we have negative amount of fuel, we need to refuel at some station previously, we choose the biggest one, increase answer
  4. If it happen, that we can not reach zero level, it means we are stuck and we can return -1 immediately.
  5. Push new amount of fuel to our heap for just visited station.

Question What happens if we have situation like this? -----10-------9--!---, we are at the moment at place ! and we meet two stations previously with fuel 9 recently and with fuel 10 some time ago. Then it seems like it is better to refuel at station with 9. However it is not the case and I spend some time realizing it. If we change from station with 9 to station with 10, when we reach !, we will have more fuel, because we always travel the same distance, but now we have more fuel in our tank.

Complexity

Time complexity is O(n log n), space complexity is O(n).

Code

class Solution:
    def minRefuelStops(self, target, fuel, s):
        heap = [] 
        s = [(0, 0)] + s + [(target, 0)]
        n, ans = len(s), 0
        
        for i in range(1, n):
            fuel -= s[i][0] - s[i-1][0]
            while heap and fuel < 0:
                fuel -= heappop(heap)
                ans += 1
            if fuel < 0: return -1
            heappush(heap, -s[i][1])
            
        return ans