Minimum Number of Refueling Stops

Patrick Leaton
Published: Nov. 17, 2021, 10:25 p.m.
Problem Description

A car travels from a starting position to a destination which is target miles east of the starting position.

There are gas stations along the way. The gas stations are represented as an array stations where stations[i] = [positioni, fueli] indicates that the ith gas station is positioni miles east of the starting position and has fueli liters of gas.

The car starts with an infinite tank of gas, which initially has startFuel liters of fuel in it. It uses one liter of gas per one mile that it drives. When the car reaches a gas station, it may stop and refuel, transferring all the gas from the station into the car.

Return the minimum number of refueling stops the car must make in order to reach its destination. If it cannot reach the destination, return -1.

Note that if the car reaches a gas station with 0 fuel left, the car can still refuel there. If the car reaches the destination with 0 fuel left, it is still considered to have arrived.

 

Example 1:

Input: target = 1, startFuel = 1, stations = []
Output: 0
Explanation: We can reach the target without refueling.

Example 2:

Input: target = 100, startFuel = 1, stations = [[10,100]]
Output: -1
Explanation: We can not reach the target (or even the first gas station).

Example 3:

Input: target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
Output: 2
Explanation: We start with 10 liters of fuel.
We drive to position 10, expending 10 liters of fuel.  We refuel from 0 liters to 60 liters of gas.
Then, we drive from position 10 to position 60 (expending 50 liters of fuel),
and refuel from 10 liters to 50 liters of gas.  We then drive to and reach the target.
We made 2 refueling stops along the way, so we return 2.

 

Constraints:

  • 1 <= target, startFuel <= 10^9
  • 0 <= stations.length <= 500
  • 0 <= positioni <= positioni+1 < target
  • 1 <= fueli < 10^9

 

The description was taken from https://leetcode.com/problems/minimum-number-of-refueling-stops/.

Problem Solution

#O(N(Log(N))) Time, O(N) Space
class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        stations.append((target, 0))
        stations.insert(0, (0, startFuel))
        heap = [-startFuel]
        tank, stops = 0, -1
       
        for i in range(1, len(stations)):
            tank -=  stations[i][0] - stations[i-1][0]
            while heap and tank < 0:
                tank += -heapq.heappop(heap)
                stops += 1
            if tank < 0:
                return -1
            heapq.heappush(heap, -stations[i][1])
       
        return stops

Problem Explanation

This problem is very similar to Furthest Building You Can Reach.

This question is a greedy problem.  A hint for that is when a question asks the final index that can be reached given a set of resources, or what minimum amount of resources are required for reaching a final index.

A common pattern for questions that give inputs of lists where indices are positions and their values are resources, is to not use resources until absolutely necessary, and to greedily pick the greatest resource after the fact so we are making the best choices moving along the positions.

For visualization purposes, we can picture this act as backtracking on the choice to not utilize the resource in the past and to refund that choice within the present.  

To solve this question, we can utilize a max-heap.

We can look at the distance between the current position and the previous then decrement our gas tank with that distance.  If our gas tank drops below zero, we'll take a gas refund from the greatest fuel amount that we passed which we placed in the heap prior.  If we have no fuel saved in the heap, or we emptied the heap and it wasn't enough fuel to keep us going, we'll stop and return a negative one.  Otherwise, we'll push the current positions' fuel into the heap so that we may utilize it later if we need it.

At the end of the traversal, we'll return the number of stops we took, which was the number of times we had to pop fuel from the heap to get the gas tank to or above zero.

Initially, we have a few problems to solve; can we get to the first position given the starting fuel amount, can we get to each additional position given the fuel amounts gained from each prior position, and can we get from the last position to the target given how much fuel is left in the tank and heap?

To merge these problems into one, we can append the target position into the stations' list, and also prepend the starting position as well.

This way, we just have one problem to solve; can we get to the current position from the previous one?

We'll append the target position stations list with a fuel amount of zero, since fuel will no longer be required after reaching that point.

We'll also prepend the source position with the starting fuel amount.

        stations.append((target, 0))
        stations.insert(0, (0, startFuel))

 

Since we are going to be checking if we can get to the current position from the previous one, we'll initialize our heap with the starting fuel amount so that this is the first fuel amount we will fill up with.

Python heaps are min-heaps by default, so to create a make-shift max-heap from a min-heap, we'll make the values negative so that the largest positive value will become the smallest when negative.

        heap = [-startFuel]

 

After, we'll initialize our gas tank fuel amount, and the number of stops we took, which will be a negative one since we're going to fill up with the starting fuel, and that doesn't actually count as a station.

        tank, stops = 0, -1

 

Next, we'll traverse the stations.

        for i in range(1, len(stations)):

 

We'll calculate the distance from the current position from the previous one, and decrement that distance from the tank.

            tank -=  stations[i][0] - stations[i-1][0]

 

If that distance dropped the tank below zero, we're going to need a gas refund.

While we still have gas in our heap and the tank is below zero, we will pop the greatest fuel from the heap and increment our stops.

            while heap and tank < 0:
                tank += -heapq.heappop(heap)
                stops += 1

 

If we emptied the heap and we are still below zero, we can't go any further so we will return a negative one.

            if tank < 0:
                return -1

 

Otherwise, we'll push the current fuel amount into the heap so that we may utilize it later if we need to.

            heapq.heappush(heap, -stations[i][1])

 

If we never returned a negative one, then we were able to reach the final position, the target.

If that is the case, we'll return the number of stops we took.

        return stops