Minimum Number of Refueling Stops
Hard · Heap & Counting · Array · Dynamic Programming · Greedy · Heap (Priority Queue)
Problem
A car drives east from position 0 toward a destination target miles away. It starts with startFuel litres, burns one litre per mile, and has an unlimited tank.
Along the way are gas stations stations[i] = [position_i, fuel_i], sorted by position. When the car stops at a station it takes all of that station's fuel. Reaching a station or the destination with exactly 0 fuel left is fine.
Return the minimum number of refuelling stops needed to reach target, or -1 if it is impossible.
Examples
Input: target = 50, startFuel = 20, stations = [[10,10],[20,30],[40,5]] Output: 1
Drive to mile 20 with an empty tank, take 30 litres there, and reach mile 50.
Input: target = 10, startFuel = 3, stations = [[5,10]] Output: -1
The car runs dry at mile 3, before the only station.
Input: target = 8, startFuel = 8, stations = [] Output: 0
The starting fuel is exactly enough.
Constraints
- 1 <= target, startFuel <= 10^9
- 0 <= len(stations) <= 500
- 1 <= position_i < position_{i+1} < target
- 1 <= fuel_i < 10^9
Approaches
- Baseline: DP over the number of stops — time O(n²), space O(n)
Follow-up
The DP baseline also answers more than the question asked: far[t] for every number of stops. The use cases flip the question (with at most k stops, how far can the car get?) and apply the same "undo the worst choice so far" heap to keeping prefix sums non-negative.
Related problems
Start free on Cariara · Coding problems · System design studio
