LeetCode 871: Minimum Number of Refueling Stops

Problem Restatement

A car starts at position 0 and needs to reach a destination target miles away.

The car starts with startFuel liters of fuel.

It consumes:

1 liter of fuel per mile

There are gas stations along the way.

Each station is represented as:

[position, fuel]

When the car reaches a station, it may stop and take all fuel from that station.

The tank has infinite capacity.

Return the minimum number of refueling stops needed to reach the destination.

If the car cannot reach the destination, return -1.

Reaching a station or the destination with exactly 0 fuel is allowed.

Input and Output

Function shape:

class Solution:
    def minRefuelStops(
        self,
        target: int,
        startFuel: int,
        stations: list[list[int]],
    ) -> int:
        ...

Examples

Example 1:

target = 1
startFuel = 1
stations = []

The car can reach the destination immediately.

So the answer is:

0

Example 2:

target = 100
startFuel = 1
stations = [[10, 100]]

The first station is at position 10, but the car can only drive 1 mile.

So the answer is:

-1

Example 3:

target = 100
startFuel = 10
stations = [[10, 60], [20, 30], [30, 30], [60, 40]]

One optimal trip is:

The answer is:

2

First Thought: Dynamic Programming

One possible solution is dynamic programming.

Let:

dp[t]

mean the farthest distance we can reach using exactly t refueling stops.

For every station, we update dp.

This works, but it costs:

O(n^2)

There is a more direct greedy solution using a heap.

Key Insight

We do not need to decide immediately whether to refuel at a station.

When we pass a station, we can remember its fuel amount.

Later, if we cannot reach the next station or destination, we choose the largest fuel amount among all stations we have already passed.

This is valid because choosing a larger past fuel amount always gives at least as much reach as choosing a smaller one, and both choices count as one stop.

So we use a max heap.

The heap stores fuel amounts from stations that are already reachable.

Whenever current fuel cannot reach the next point, we refuel from the largest available past station.

Algorithm

Treat the destination as one final station with 0 fuel:

stations.append([target, 0])

Maintain:

fuel = startFuel
prev_position = 0
stops = 0
max_heap = []

For each station:

1. Compute the distance from the previous position.
2. Spend that much fuel.
3. While fuel is negative:
   1. If the heap is empty, return -1.
   2. Pop the largest fuel amount from the heap.
   3. Add it to fuel.
   4. Increase stops.
4. Push the current station’s fuel into the heap.
5. Update prev_position.

The heap uses negative numbers because Python has a min heap.

Correctness

The algorithm processes stations in increasing position order, so when it reaches a station, every fuel amount in the heap comes from a station already passed.

If the car has enough fuel to reach the current station, no stop is needed yet.

If the car does not have enough fuel, then any valid trip must have refueled at one of the stations already passed. Choosing the station with the largest available fuel is optimal for the current stop because it maximizes the car’s remaining reach while using only one stop.

If even after using all passed stations the car cannot reach the current station, then no valid route can reach it, so returning -1 is correct.

Each time the algorithm refuels, it uses one station that was reachable before the failure point. This matches a valid retroactive choice: we can interpret the heap pop as deciding that we had stopped at that earlier station.

By always delaying stops until necessary and then choosing the largest available fuel, the algorithm uses the fewest possible stops to reach each point. Therefore, when it reaches the destination, the stop count is minimal.

Complexity

Let:

n = len(stations)

Implementation

import heapq

class Solution:
    def minRefuelStops(
        self,
        target: int,
        startFuel: int,
        stations: list[list[int]],
    ) -> int:
        max_heap = []
        fuel = startFuel
        prev_position = 0
        stops = 0

        stations.append([target, 0])

        for position, station_fuel in stations:
            distance = position - prev_position
            fuel -= distance

            while fuel < 0:
                if not max_heap:
                    return -1

                fuel += -heapq.heappop(max_heap)
                stops += 1

            heapq.heappush(max_heap, -station_fuel)
            prev_position = position

        return stops

Code Explanation

We start with the initial state:

max_heap = []
fuel = startFuel
prev_position = 0
stops = 0

The heap stores fuel from stations we have already reached.

We append the destination as a station with no fuel:

stations.append([target, 0])

This lets the same logic handle reaching the target.

For each station:

for position, station_fuel in stations:

we compute the distance from the previous point:

distance = position - prev_position
fuel -= distance

If fuel becomes negative, the car could not reach this station with the current choices.

So we refuel from the best previous station:

while fuel < 0:
    if not max_heap:
        return -1

    fuel += -heapq.heappop(max_heap)
    stops += 1

Because Python’s heap is a min heap, fuel amounts are stored as negative values.

After we can reach the current station, we add its fuel as an option for later:

heapq.heappush(max_heap, -station_fuel)

Then we update the previous position:

prev_position = position

After processing the destination, return the number of stops:

return stops

Testing

def test_min_refuel_stops():
    s = Solution()

    assert s.minRefuelStops(1, 1, []) == 0

    assert s.minRefuelStops(100, 1, [[10, 100]]) == -1

    assert s.minRefuelStops(
        100,
        10,
        [[10, 60], [20, 30], [30, 30], [60, 40]],
    ) == 2

    assert s.minRefuelStops(
        100,
        50,
        [[25, 25], [50, 25], [75, 25]],
    ) == 2

    assert s.minRefuelStops(
        100,
        25,
        [[25, 25], [50, 25], [75, 25]],
    ) == 3

    print("all tests passed")

test_min_refuel_stops()

Test meaning: