{x}
blog image

Minimum Number of Refueling Stops

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 <= 109
  • 0 <= stations.length <= 500
  • 1 <= positioni < positioni+1 < target
  • 1 <= fueli < 109

Minimum Number of Refueling Stops

This problem asks for the minimum number of refueling stops needed to reach a target distance, given an initial fuel amount and a list of gas stations with their positions and fuel amounts.

Approach: Greedy with Priority Queue

The optimal solution uses a greedy approach combined with a priority queue (max-heap). The idea is to prioritize refueling at stations that offer the most fuel. This ensures we maximize our fuel capacity and minimize the number of stops.

  1. Initialization: We start with the initial fuel (startFuel) and a priority queue (pq) to store fuel amounts at visited gas stations. We also append a dummy station at the target distance with 0 fuel to simplify the loop.

  2. Iteration: We iterate through the gas stations (including the dummy target station). For each station:

    • Calculate the distance to the current station from the previous location.
    • Subtract this distance from our current fuel.
    • If our fuel becomes negative, we need to refuel. We repeatedly pop the largest fuel amount from the priority queue (pq) and add it to our fuel until our fuel is non-negative. This greedy selection guarantees we use the most fuel-efficient stations first. If we run out of fuel in pq and still have negative fuel, it means we can't reach the destination, and we return -1.
    • Add the current station's fuel to the priority queue.
    • Update the previous location to the current station's position.

  3. Result: The number of times we refueled (ans) is our final answer.

Time and Space Complexity

  • Time Complexity: O(N log N), where N is the number of gas stations. The dominant factor is the priority queue operations (push and pop), which take logarithmic time.

  • Space Complexity: O(N), due to the priority queue storing at most N fuel amounts.

Code Implementation (Python)

import heapq
 
class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        pq = []  # Priority queue (max-heap) to store fuel amounts
        ans = 0  # Number of refueling stops
        curr_fuel = startFuel  # Current fuel level
        prev_pos = 0  # Position of the previously visited station (or starting point)
 
        stations.append([target, 0])  # Add a dummy station at the target
 
        for pos, fuel in stations:
            dist = pos - prev_pos  # Distance to the current station
            curr_fuel -= dist  # Consume fuel for the journey
 
            # If fuel is insufficient, refuel from the priority queue
            while curr_fuel < 0 and pq:
                curr_fuel += heapq.heappop(pq)  # Add the largest fuel amount
                ans += 1  # Increment the number of stops
 
            if curr_fuel < 0:
                return -1  # Cannot reach the destination
 
            heapq.heappush(pq, -fuel)  # Add the current station's fuel (negative for max-heap)
            prev_pos = pos  # Update the previous position
 
        return ans

The code in other languages (Java, C++, Go, TypeScript, Rust) follows a similar structure, utilizing their respective priority queue implementations. The core logic of the greedy approach with a priority queue remains consistent across all languages.