HardArrayDynamic ProgrammingGreedyHeapUpdated Sep 2026

871. Minimum Number of Refueling Stops

Asked at Uber, DE Shaw

Difficulty

Hard

Time

O(n log n)

Space

O(n)

Pattern

Array

Companies

2

Problem

A car starts at mile 0 and must reach a point target miles away. It burns 1 liter of fuel per mile. It starts with startFuel liters and has an unlimited tank size.

Along the road there are gas stations. Each station is given as stations[i] = [position, fuel]: it sits at that mile marker and holds that many liters. When the car stops at a station, it takes all the fuel there. You may skip stations, and you may stop at a station even if you arrive with exactly 0 fuel left.

Return the minimum number of refueling stops needed to reach the target. If no set of stops gets the car there, return -1. Reaching the target with exactly 0 fuel still counts as arriving.

The road and its fuel stations

stations[10,60][20,30][30,30][60,40]0123The best plan stops at mile 10 and mile 60 — the twobiggest fuel tanks.start: 10 L at mile 0mile 10: fuel 0, take 60mile 60: fuel 10, take 40mile 100: arrive, 2 stopsTwo stops are enough; stopping anywhere else needsmore stops or fails.
The car must cover 100 miles starting with 10 liters; each station offers a different amount of fuel.

Constraints

  • ●1 <= target, startFuel <= 10^9
  • ●0 <= stations.length <= 500
  • ●1 <= position_i < position_{i+1} < target
  • ●1 <= fuel_i < 10^9

Examples

Example 1
Inputtarget = 1, startFuel = 1, stations = []
Output0
WhyThe car has exactly enough fuel to cover the 1 mile, so it never needs to stop.
Example 2
Inputtarget = 100, startFuel = 1, stations = [[10,100]]
Output-1
WhyWith only 1 liter the car can drive 1 mile, but the first station is 10 miles away. It runs dry before it can refuel anywhere.
Example 3
Inputtarget = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
Output2
WhyDrive 10 miles to the first station (fuel hits 0), take its 60 liters. Drive 50 miles to the station at mile 60 (fuel drops to 10), take its 40 liters. Now 50 liters remain, which is enough for the last 40 miles. Two stops total.

Asked At

2 companies
CompanyDifficulty
UberHardView all Uber questions →
DE ShawHardView all DE Shaw questions →

How to Think About It

1

Brute force: try every subset of gas stations to refuel at, check which subsets allow reaching the destination.

2

Notice that at each stop, you want to choose the station that gives you the most fuel. This suggests a greedy approach.

3

Use a max-heap to track all stations you have passed. When you run out of fuel, greedily pick the station with the most fuel.

4

Drive forward, adding passed stations to the heap. When current fuel drops below zero, pop the max from the heap and refuel.

5

If the heap is empty when you need fuel, return -1. The number of pops equals the minimum stops.

Optimal Approach

Use a max-heap to greedily refuel. Sort stations by position. Drive forward, subtracting distance from fuel. Whenever you pass a station, push its fuel into the heap. When fuel goes negative, pop the largest fuel amount from the heap and add it to fuel, incrementing stops. If the heap is empty when fuel is negative, return -1. This greedy approach works because at each point where you need fuel, taking the maximum available from all previously passed stations is optimal.

Greedy refuel with a max-heap

stations[10,60][20,30][30,30][60,40]0123nextDrive to mile 10: fuel 10 − 10 = 0, so push 60 intothe heap.max-heap (passed stations)60← topTank is empty, so pop 60: fuel becomes 60 and stopsbecomes 1.max-heap (passed stations)403030← topAfter mile 60 the tank is 10, so pop 40: fuel becomes50 and stops becomes 2.fuel -= distance to next pointwhile fuel < 0: fuel += pop_max()if heap empty and fuel < 0: return -1
Keep every passed station in a max-heap and only refuel when the tank goes negative, always taking the biggest tank seen so far.
ComplexityTime O(n log n)Space O(n)Each station is pushed into the heap once and popped at most once, so the heap work is O(n log n); n is the number of stations.

What Trips People Up in Real Interviews

1

Clarify whether stations are sorted by position (usually yes). Ask about the fuel capacity.

2

Start with the DP approach: dp[i] = max distance reachable with i stops.

3

Then optimize to greedy with a heap — explain why the greedy choice is optimal.

4

Draw a number line with stations and simulate the algorithm step by step.

5

Discuss time complexity: O(n log n) for the heap approach.

Solution Code

O(n log n) time
import heapq

def minRefuelStops(target, startFuel, stations):
    pq = []
    stations.append([target, 0])
    fuel = startFuel
    stops = 0
    prev = 0
    for position, gas in stations:
        fuel -= position - prev
        while fuel < 0 and pq:
            fuel += -heapq.heappop(pq)
            stops += 1
        if fuel < 0:
            return -1
        heapq.heappush(pq, -gas)
        prev = position
    return stops

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Minimum Number of Refueling Stops problem?

A car travels from a starting position to a destination with a given fuel capacity. There are gas stations along the way, each at a certain position and with a certain amount of fuel. Find the minimum number of refueling stops needed to reach the destination, or return -1 if impossible.

How do you solve Minimum Number of Refueling Stops?

The optimal approach runs in O(n log n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Minimum Number of Refueling Stops?

Minimum Number of Refueling Stops is asked at Uber, DE Shaw. It is a hard difficulty problem.

What are common mistakes on Minimum Number of Refueling Stops?
  • Clarify whether stations are sorted by position (usually yes). Ask about the fuel capacity.
  • Start with the DP approach: dp[i] = max distance reachable with i stops.
  • Then optimize to greedy with a heap — explain why the greedy choice is optimal.
  • Draw a number line with stations and simulate the algorithm step by step.
  • Discuss time complexity: O(n log n) for the heap approach.