Machine Learning, AI and Programming

LeetCode: Minimum Refuel Stops

Problem Statement


At first, this looks like a classic graph traversal problem. For example, I might be tempted to use BFS approach to find the minimum number of steps to reach the target. But one important distinction this problem has from a standard BFS is that in a standard BFS problem, the car can either directly reach a station Y from station X or they cannot depending whether there is an edge between them, but in this problem, the car can reach station Y from station X depending on how much amount of fuel the car has when it is at station X and the amount of fuel in the car at any moment depends upon the path taken. Thus standard BFS approach will not fit here and we might think that we need to exhaustively search for all possible paths.

So let's look at an alternative approach. If we can compute a function F(i, j) which represents the maximum possible distance the car can travel from station i after it has taken j steps to reach i from the source, then for all stations k, such that F(k, j) >= target, we can select the minimum number of steps as the value of j which is minimum, plus 1 due to the hop from k to target, i.e.

minimum number of steps = argmin {j | F(k, j) >= target} + 1

One can compute F(i, j) using a dynamic programming approach i.e. for all stations i' < i, if F(i', j-1) >= di where di is the distance of station i from source, then:

F(i, j) = max {F(i', j-1) | F(i', j-1) >= di} + fi

where fi is the amount of fuel available at station i. Intuitively speaking F(i, j) can be found by looking at all F's at step j-1 for all stations i' located before i. Then select the maximum among these and add the current fuel amount at station i.

Observe that to compute F(i, j) we only need to obtain the maximum F at step j-1 irrespective of the station. Thus we only need to track the maximum value of F for any step j. The run-time of this approach is O(N2) where N is the total number of stations, because at each station i, we update the maximum value of F for each step. Since the maximum number of steps is O(N), the run-time is O(N2).

def minRefuelStops(target, startFuel, stations):
    n = len(stations)
    max_dist = [-1]*n
    for i in range(n):
        for step in reversed(range(i+1)):
            w = startFuel if step == 0 else max_dist[step-1]
            if w >= stations[i][0]:
                max_dist[step] = max(max_dist[step], w + stations[i][1])
    for i in range(n):
        if max_dist[i] >= target:
            return i+1
    return -1

In the above code, the array 'max_dist' is the function F in our definition above. Observe that although F was a function of 2 variables (station and number of steps) but 'max_dist' is an array of only the number of steps as a variable. This is because we do not need to store 'max_dist' for each station i and each number of steps j but only the maximum value for each j which we update at each station i.

Also observe that the nested for-loop on 'step' is in reversed order because we want to update the value of 'max_dist[step]' from 'max_dist[step-1]' computed at the previous station and not 'max_dist[step-1]' computed at the current station, which will be the case if we iterate in an increasing order of steps.

But this run-time can also be improved. One of my mistakes was assuming that the car can only travel in the forward direction and cannot travel to any station i' from any station i > i'. If we remove this assumption, then finding the solution is just a greedy algorithm, i.e. at each step go to the station (reachable) with the highest fuel capacity.

From a station i, the car would prefer to travel to a station j, with the highest fuel capacity among all stations reachable from i. Thus we keep a max-heap of the currently un-explored stations and the root storing the station that is having the maximum fuel among the un-explored stations. Repeat this by 'exploring' the root station each time until the maximum possible distance >= target.

This approach is having a run-time of O(N*logN).

import heapq

def minRefuelStops(target, startFuel, stations):
    queue, max_dist, step, index = [], startFuel, 0, 0
    while True:
        while index < len(stations) and stations[index][0] <= max_dist:
            heapq.heappush(queue, -stations[index][1])
            index += 1

        if max_dist >= target:
            return step
        if len(queue) == 0:
            return -1
        max_dist += -heapq.heappop(queue)
        step += 1


Tags: , , , , ,