Skip to main content

871 - Minimum Number of Refueling Stops

Difficulty: Hard | Pattern: Greedy + Max-Heap | Company tags: Amazon, Google, Uber

Problem Statement​

A car travels from a starting position to a destination which is target miles away.

Along the way, there are gas stations at positions stations[i] = [position, fuel]. Note that fuel is in liters.

The car starts with an infinite tank but a finite initial fuel. The car uses 1 liter per mile.

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

Example 1:

Input: target=100, startFuel=10, stations=[[10,60],[20,30],[30,30],[60,40]]
Output: 2

Approach: Greedy + Max-Heap — O(n log n)​

Key insight: Drive as far as possible. When you can't continue, "retrospectively" pick the largest fuel you passed. This is optimal because we're maximizing fuel gained per stop.

import heapq

def minRefuelStops(target: int, startFuel: int, stations: list[list[int]]) -> int:
    fuel = startFuel
    stops = 0
    prev = 0
    heap = []  # max-heap (negate values)
    
    for position, gas in stations + [[target, 0]]:
        fuel -= position - prev  # drive to this station
        
        while heap and fuel < 0:
            fuel += -heapq.heappop(heap)  # use largest fuel seen so far
            stops += 1
        
        if fuel < 0:
            return -1
        
        heapq.heappush(heap, -gas)
        prev = position
    
    return stops

Algorithm Flow​

Dry Run​

target=100, startFuel=10, stations=[[10,60],[20,30],[30,30],[60,40]]

We drive station-to-station. Whenever fuel drops below 0, we pop the largest fuel amount seen so far (one stop) and repeat until fuel >= 0.

positiondrive costfuel after drivingactionfuel (end)stopsheap after
1010 - 0 = 100fuel ≥ 0, no pop; push 6000[60]
2020 - 10 = 10-10pop 60 → -10 + 60 = 50 (stop); push 30501[30]
3030 - 20 = 1040fuel ≥ 0, no pop; push 30401[30, 30]
6060 - 30 = 3010fuel ≥ 0, no pop; push 40101[40, 30, 30]
100 (target)100 - 60 = 40-30pop 40 → -30 + 40 = 10 (stop); 10 ≥ 0, stop popping102[30, 30]

At the virtual target station, one pop of the largest passed fuel (40) is enough: -30 + 40 = 10, which is non-negative, so the while loop halts immediately. Final answer: 2 stops.

Note that the heap deliberately holds fuel values we passed but never needed (the two 30s here). That is the point of the retrospective approach — those stations stay available as options but cost us nothing because we never popped them.

Complexity​

  • Time: O(n log n)
  • Space: O(n)

Key Terms​

TermDefinition
GreedyMaking the locally optimal choice at each step, trusting it leads to a globally optimal solution.
Max-heapA priority queue that always exposes the largest element; here it tracks the biggest fuel amount passed but not yet used.
Retrospective selectionDeferring a decision (which station to "use") until it's forced, then picking the best option seen so far.
Amortized stop countThe number of refuels is bounded by the number of stations, since each station is pushed/popped at most once.

FAQ​

  1. Why use a max-heap instead of trying every subset of stations? Trying subsets is exponential. The greedy insight — always keep the option to "retroactively" use the largest fuel passed — lets a single pass with a heap reach the optimal answer in O(n log n).
  2. Can this be solved without extra space? Not efficiently while keeping O(n log n) time — the heap is what lets you defer the choice of which station to use. A DP approach (max distance reachable with k stops) avoids a heap but uses O(n) space too, trading time for a different structure.
  3. What if startFuel >= target already? The loop still runs correctly: fuel never goes negative, so stops stays 0 and the function returns immediately with 0 stops.
  4. What if the car can never reach the target? Once fuel goes negative and the heap is empty (no more stations to draw fuel from), the function returns -1.
  5. What's the common follow-up interviewers ask? "What's the maximum distance reachable with at most k stops?" — this flips the problem into a DP formulation: dp[k] = farthest distance reachable using exactly k stops, updated greedily as stations are processed in order.

Quick Revision​

  • Pattern: Greedy + Max-Heap ("retroactive" greedy).
  • Process stations in position order; subtract distance traveled from current fuel.
  • If fuel goes negative, pop the largest fuel value from the heap (best station passed so far) and add it — that's one stop.
  • If fuel still negative after exhausting the heap, destination is unreachable → return -1.
  • Push each station's fuel onto the heap after "arriving" at it, whether or not it's used yet.
  • Append a virtual station [target, 0] to trigger the final check.
  • Time: O(n log n) from heap operations; Space: O(n) for the heap.
  • Each station is pushed and popped at most once, bounding total heap work.
  • Alternative: DP where dp[k] tracks max distance reachable with k refuels — O(n²) time, O(n) space.