Minimum Number of Refueling Stops
Asked at Uber
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Uber | HARD | View all Uber questions → |
How to Think About It
Brute force: try every subset of gas stations to refuel at, check which subsets allow reaching the destination.
Notice that at each stop, you want to choose the station that gives you the most fuel. This suggests a greedy approach.
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.
Drive forward, adding passed stations to the heap. When current fuel drops below zero, pop the max from the heap and refuel.
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.
What Trips People Up in Real Interviews
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.
Solution Code
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 stopsFrequently 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Minimum Number of Refueling Stops?
Minimum Number of Refueling Stops is asked at Uber. 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.