# 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:

```python
1 liter of fuel per mile
```

There are gas stations along the way.

Each station is represented as:

```python
[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

| Item | Meaning |
|---|---|
| Input | `target`, the destination distance |
| Input | `startFuel`, the initial fuel |
| Input | `stations`, where each station is `[position, fuel]` |
| Output | Minimum number of refueling stops |
| Failure case | Return `-1` if reaching `target` is impossible |

Function shape:

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

## Examples

Example 1:

```python
target = 1
startFuel = 1
stations = []
```

The car can reach the destination immediately.

So the answer is:

```python
0
```

Example 2:

```python
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:

```python
-1
```

Example 3:

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

One optimal trip is:

| Step | Action | Reachable fuel state |
|---|---|---|
| Start | Fuel is `10` | Can reach position `10` |
| Station `10` | Refuel `60` | Stop count `1` |
| Station `60` | Refuel `40` | Stop count `2` |
| Destination | Reach position `100` | Done |

The answer is:

```python
2
```

## First Thought: Dynamic Programming

One possible solution is dynamic programming.

Let:

```python
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:

```python
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:

```python
stations.append([target, 0])
```

Maintain:

```python
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:

```python
n = len(stations)
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(n log n)` | Each station fuel is pushed once and popped at most once |
| Space | `O(n)` | The heap may store fuel from many reachable stations |

## Implementation

```python
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:

```python
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:

```python
stations.append([target, 0])
```

This lets the same logic handle reaching the target.

For each station:

```python
for position, station_fuel in stations:
```

we compute the distance from the previous point:

```python
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:

```python
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:

```python
heapq.heappush(max_heap, -station_fuel)
```

Then we update the previous position:

```python
prev_position = position
```

After processing the destination, return the number of stops:

```python
return stops
```

## Testing

```python
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:

| Test | Why |
|---|---|
| `target = 1`, `startFuel = 1` | Already reaches destination |
| Cannot reach first station | Immediate failure |
| Standard multi-station case | Requires choosing large prior fuel |
| Enough initial fuel for first half | Checks delayed refueling |
| Arrives at stations with exactly zero fuel | Exact zero fuel is valid |