Prompt and context
This is a resource-constrained greedy problem. Fuel can be taken only from stations already passed, and the objective is the number of stops rather than total fuel. A strong interview answer connects reachability, lazy decisions, the max-heap invariant, and the final segment from the last station to the target.
What the interviewer evaluates
- Whether you turn “refuel only when necessary” into a lazy greedy strategy.
- Whether you prove that taking the largest passed fuel cannot increase the optimal stop count.
- Whether you handle the start, target, duplicate positions, and unreachable cases.
- Whether you provide an O(n log n) time and O(n) space implementation.
Clarifying questions
Confirm that stations are ordered by position, whether duplicate positions are allowed, that fuel is non-negative, and whether the target itself is a station. Ask about input size and integer range. The default model starts at position 0 and allows fuel from a station only after reaching it.
30-second answer outline
Scan stations by position and push every passed fuel amount into a max heap. Before reaching each next station or the target, subtract the distance. If fuel becomes negative, a stop is forced, so repeatedly pop the largest passed fuel and increment the stop count. If the heap is empty, return -1. Choosing the largest available fuel at each forced stop maximizes the reachable distance without increasing the number of stops.
Step-by-step solution
1. Establish the reachability invariant
At position p, the heap contains fuel from every station at or before p, while fuel is the unused amount. If the fuel amount is negative, progress is impossible without using one of those stations. Each pop extends the reachable range until the fuel amount is non-negative again.
2. Prove the lazy greedy choice
Suppose an optimal plan chooses a smaller passed amount a when it must refuel, while a larger amount b is available. Replace a with b: the stop count is unchanged and the remaining fuel after this point does not decrease, so every later segment remains feasible. Repeating this exchange yields an equally optimal plan that always chooses the maximum.
3. Treat the target as a boundary
Append a virtual station (target, 0) and process it exactly like every other position. Start from position 0, subtract each distance, and only then add the station’s fuel. If the target still requires a pop, those stops count; an empty heap while fuel is negative means the target is unreachable.
4. Implement the heap
Python heapq is a min heap, so negative fuel values simulate a max heap. Each station is pushed once and popped only when a stop is required:
import heapq
def min_refuel_stops(target, start_fuel, stations):
fuel = start_fuel
previous = 0
max_heap = []
stops = 0
for position, station_fuel in [*stations, (target, 0)]:
fuel -= position - previous
while fuel < 0 and max_heap:
fuel += -heapq.heappop(max_heap)
stops += 1
if fuel < 0:
return -1
heapq.heappush(max_heap, -station_fuel)
previous = position
return stops5. Analyze complexity and boundaries
With n stations, each fuel value enters and leaves the heap at most once, giving O(n log n) time and O(n) heap space. Test sufficient initial fuel, an unreachable first station, a required stop after the last station, zero fuel, duplicate positions, an exact target arrival, and an unreachable target.
Model high-quality answer
I would append the target as a zero-fuel virtual station. During the scan, subtract travel distance and push fuel from stations already reached. Whenever remaining fuel is negative, a stop is forced; repeatedly take the largest historical fuel until the current position is reachable. An empty heap means -1. The exchange proof replaces any smaller chosen passed fuel with a larger available one without increasing stops or reducing future reachability. Each station is pushed and popped at most once, so the complexity is O(n log n) time and O(n) space.
Common mistakes
- Refueling immediately at every station instead of delaying the decision.
- Checking only station-to-station gaps and forgetting the final target gap.
- Mixing current unused fuel with fuel available in the heap.
- Using a min heap and taking the smallest amount.
- Adding a station before reaching it and using future fuel early.
- Testing only reachable examples and missing empty-heap or numeric boundaries.
Follow-up questions
Why not take the maximum at every station?
The objective is stop count. Early refueling can add stops without improving reachability. Delaying until fuel is insufficient ensures every stop answers a real constraint.
What changes if partial refueling is allowed?
The state and cost function change. Prices or tank capacity may matter, so the proof for taking an entire station’s fuel no longer applies directly.
Why do duplicate positions work?
Their distance is zero, so they can be pushed in any order. The heap still exposes the largest available amount when a later segment actually requires fuel.
How would you return the actual stops?
Store the station index with each heap value and record the index whenever it is popped. Sort the recorded indices by position or selection order to reconstruct the route.