We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Number of Refueling Stops

Number: 902

Difficulty: Hard

Paid? No

Companies: Amazon, Bloomberg, Google, Goldman Sachs, DE Shaw, Snap, Barclays, Rubrik, Microsoft

Problem Description

A car must travel from a starting point to a destination that is target miles away. The car starts with startFuel liters of fuel and consumes one liter per mile. Along the way, there are several gas stations available, where each station is denoted by its position and the amount of fuel it provides. The task is to determine the minimum number of refueling stops required to reach the destination. If the destination cannot be reached, return -1.

Key Insights

  • The car's fuel depletes as it travels, so fuel management is critical.
  • Using a greedy strategy with a max-heap (priority queue) helps decide from which station to refuel.
  • At each station, if the current fuel is insufficient to reach the next station (or the destination), refuel from the station with the maximum fuel among all previously passed stations.
  • Dynamic programming can also be used, but a greedy approach with a heap usually yields a simpler solution.
  • Edge cases: no stations available, or fuel exactly reaches a station/destination with 0 fuel remaining.

Space and Time Complexity

Time Complexity: O(n log n) where n is the number of stations. Each station may be pushed or popped from the heap. Space Complexity: O(n) due to the storage used by the heap for up to n elements.

Solution

The solution uses a greedy approach combined with a max-heap. As the car moves towards the target, it subtracts the distance traveled from its current fuel. Whenever the fuel is insufficient to travel to the next station or destination, the algorithm refuels using the station that offered the most fuel among those passed (available in the max-heap). If no such station exists and the car cannot proceed further, the destination is unreachable (return -1). This approach minimizes the number of stops since we always choose the best available fuel option when needed.

Code Solutions

import heapq

def minRefuelStops(target, startFuel, stations):
    # Max-heap to store the fuels available at the stations we've passed.
    max_heap = []
    numRefuels = 0
    prev_position = 0
    fuel = startFuel
    
    # Append target as a final station to unify logic
    stations.append([target, 0])
    
    for position, station_fuel in stations:
        # Calculate distance from previous station (or start) to current station.
        distance = position - prev_position
        
        # While we don't have enough fuel to reach the current station,
        # refuel from the stations previously passed (using max fuel from heap).
        while fuel < distance and max_heap:
            added_fuel = -heapq.heappop(max_heap)  # Retrieve max fuel available
            fuel += added_fuel
            numRefuels += 1
        
        # If we still can't reach the station, return -1.
        if fuel < distance:
            return -1
        
        # Subtract the fuel used to travel to this station.
        fuel -= distance
        # Store the fuel available at this station into the max-heap.
        heapq.heappush(max_heap, -station_fuel)
        # Update prev_position for next iteration.
        prev_position = position
    
    return numRefuels

# Example usage:
print(minRefuelStops(100, 10, [[10,60],[20,30],[30,30],[60,40]]))  # Expected output: 2
← Back to All Questions