Minimum Number of Refueling Stops
Explanation & Solution
Description
A car starts at position 0 with startFuel liters of fuel in its tank. It needs to travel to a position target miles east. Along the way there are gas stations, where stations[i] = [position_i, fuel_i] indicates that the i-th gas station is at position_i miles east and has fuel_i liters of fuel.
The car uses one liter of fuel per mile driven. When the car reaches a gas station it may stop and refuel, transferring all the fuel from that station into the car.
Return the minimum number of refueling stops the car must make to reach the target. If it cannot reach the target, return -1.
Input: target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
Output: 2
Explanation: We start with 10 liters of fuel. We drive to station 0 (position 10), refuel 60 liters (tank = 60). We drive to station 3 (position 60), refuel 40 liters (tank = 40). We drive to target (position 100). We made 2 refueling stops.
Constraints
1 <= target, startFuel <= 10^90 <= stations.length <= 5001 <= position_i < target1 <= fuel_i < 10^9stationsis sorted byposition_iin ascending order
Approach
Greedy Techniques pattern
1. Model the Problem as a Greedy Choice
- We drive as far as we can on our current fuel. Whenever we pass a station, we remember the fuel it offers (add it to a max-heap) but do not necessarily stop there.
- Only when we run out of fuel before reaching the target do we retroactively refuel at the station that offered the most fuel.
2. Build a Max-Heap of Available Fuel
- Iterate through the stations in order. For each station whose position is within our current reach (position <= current fuel range), push that station's fuel amount onto a max-heap.
- The heap always contains fuel values from stations we have passed but not yet used.
3. Refuel When Stuck
- If our current fuel is not enough to reach the target, pop the largest value from the heap. This is equivalent to stopping at the best station we already drove past.
- Add that fuel to our tank and increment the stop counter by 1.
- Repeat: after refueling, more stations may now be reachable, so add those to the heap as well.
4. Detect Impossibility
- If at any point we cannot reach the target and the heap is empty (no more stations to draw fuel from), return
-1.
5. Return the Stop Count
- Once our fuel is >= target, we have enough to finish the trip. Return the total number of stops made.
Key Insight
- The greedy + max-heap approach works because refueling at a station costs the same no matter when we decide to use it (one stop). So delaying the decision and always picking the station with the most fuel minimizes the total number of stops. The max-heap lets us efficiently retrieve the best unused station in O(log n) time, giving an overall time complexity of O(n log n) and space complexity of O(n).