LeetCode 871 - Minimum Number of Refueling Stops

LeetCode Problem 871

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Greedy, Heap (Priority Queue)

Solution

Problem Understanding

The problem describes a car traveling from position 0 to a destination located target miles away. The car starts with startFuel liters of fuel, and every mile driven consumes exactly one liter of fuel. Along the route, there are gas stations positioned at increasing distances from the start.

Each gas station is represented as:

stations[i] = [positioni, fueli]

where:

• positioni is the distance of the station from the start
• fueli is the amount of fuel available at that station

Whenever the car reaches a station, it may choose to stop and take all available fuel from that station. The car has an effectively infinite tank capacity, so there is no upper bound on how much fuel it can hold.

The goal is to determine the minimum number of refueling stops needed to reach the destination. If reaching the destination is impossible, the algorithm must return -1.

The key challenge is that choosing where to refuel affects future reachability. A greedy choice that seems locally optimal may prevent reaching farther stations later.

The constraints are important:

• stations.length <= 500
• Fuel amounts and distances can be as large as 10^9

A station count of 500 is small enough for quadratic dynamic programming, but large enough that exponential brute force is infeasible. The large fuel and distance values also imply that simulation approaches based on individual miles are impossible.

Several edge cases are especially important:

• The car may already have enough fuel to reach the target without stopping.
• The first station may be unreachable.
• Multiple stations may be reachable before any refueling decision becomes necessary.
• Arriving at a station or target with exactly 0 fuel is still valid.
• Greedy decisions based only on the nearest or largest station can fail unless carefully structured.

Approaches

Brute Force Approach

A brute force solution would explore every possible combination of stations where refueling might occur.

At each station, there are two choices:

1. Refuel
2. Skip the station

This creates a decision tree. For every subset of stations, we can simulate whether the car successfully reaches the target and count how many stops were used. Among all valid paths, we select the minimum number of stops.

This approach is correct because it examines every possible sequence of refueling decisions. If a valid solution exists, brute force will eventually find it.

However, the time complexity is exponential. With up to 500 stations, exploring all subsets becomes completely impractical.

Optimal Greedy + Max Heap Approach

The key insight is that we do not need to decide immediately whether to refuel at a station.

Instead, as we travel forward, we can store all reachable stations in a max heap. Whenever we run out of fuel before reaching the next position, we retroactively choose the largest fuel station among all stations we have already passed.

This greedy strategy works because:

• If refueling becomes necessary, choosing the station with the most fuel maximizes future reachability.
• Delaying the decision preserves flexibility.
• Refueling earlier than necessary never provides an advantage because the tank is infinite.

The heap efficiently tracks the best available past refueling options.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Tries every subset of stations
Optimal	O(n log n)	O(n)	Greedy strategy using a max heap

Algorithm Walkthrough

Optimal Greedy Heap Algorithm

1. Initialize the current reachable distance as startFuel.

This represents the farthest distance the car can currently reach without additional refueling. 2. Create a max heap to store fuel amounts from stations already passed.

Python's heapq is a min heap, so negative values are stored to simulate max heap behavior. 3. Initialize:

• station_index = 0
• refuel_stops = 0

4. While the current reachable distance is less than the target:

We have not yet reached the destination, so we may need more fuel. 5. Add all reachable stations into the heap.

While:

• station_index < len(stations)
• stations[station_index][0] <= current_fuel

push that station's fuel into the heap.

These are stations we can already reach with our current fuel. 6. If the heap is empty at this point, return -1.

This means:

• we cannot reach the target
• and there are no previously reachable stations available for refueling

7. Pop the largest fuel amount from the heap.

This represents the best previously passed station to refuel from. 8. Add that fuel to the current reachable distance.

This extends how far the car can travel. 9. Increment the refueling stop count. 10. Repeat until the target becomes reachable. 11. Return the total number of refueling stops.

Why it works

The algorithm maintains the invariant that all stations currently in the heap are reachable using the fuel accumulated so far.

Whenever additional fuel is required, selecting the station with the maximum fuel provides the greatest possible extension of reach. Any smaller choice could only reduce future options and never improve the number of stops.

Because refueling decisions are postponed until absolutely necessary, the algorithm preserves maximum flexibility while always making the locally optimal choice. This greedy strategy can be proven optimal through an exchange argument: any optimal solution can be transformed into one that always uses the largest available station whenever refueling becomes necessary.

Python Solution

from typing import List
import heapq

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

        max_heap = []
        current_reach = startFuel
        station_index = 0
        refuel_stops = 0

        while current_reach < target:

            while (
                station_index < len(stations)
                and stations[station_index][0] <= current_reach
            ):
                fuel = stations[station_index][1]
                heapq.heappush(max_heap, -fuel)
                station_index += 1

            if not max_heap:
                return -1

            current_reach += -heapq.heappop(max_heap)
            refuel_stops += 1

        return refuel_stops

The implementation begins by initializing a max heap, which stores fuel amounts from reachable stations. Since Python's heapq only supports min heaps, negative values are pushed into the heap.

current_reach tracks the farthest distance reachable with the current fuel supply. Initially, this equals startFuel.

The outer loop continues until the destination becomes reachable. Inside the loop, all stations whose positions are less than or equal to current_reach are added to the heap. This means they are available as future refueling candidates.

If no stations are available in the heap and the target has not yet been reached, the journey is impossible, so the algorithm returns -1.

Otherwise, the algorithm greedily selects the station with the largest fuel amount by popping from the heap. That fuel is added to current_reach, and the refueling counter is incremented.

Eventually, either the target becomes reachable or the algorithm determines no valid path exists.

Go Solution

package main

import (
	"container/heap"
)

type MaxHeap []int

func (h MaxHeap) Len() int {
	return len(h)
}

func (h MaxHeap) Less(i, j int) bool {
	return h[i] > h[j]
}

func (h MaxHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *MaxHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *MaxHeap) Pop() interface{} {
	old := *h
	n := len(old)
	value := old[n-1]
	*h = old[:n-1]
	return value
}

func minRefuelStops(target int, startFuel int, stations [][]int) int {
	maxHeap := &MaxHeap{}
	heap.Init(maxHeap)

	currentReach := startFuel
	stationIndex := 0
	refuelStops := 0

	for currentReach < target {

		for stationIndex < len(stations) &&
			stations[stationIndex][0] <= currentReach {

			heap.Push(maxHeap, stations[stationIndex][1])
			stationIndex++
		}

		if maxHeap.Len() == 0 {
			return -1
		}

		currentReach += heap.Pop(maxHeap).(int)
		refuelStops++
	}

	return refuelStops
}

The Go solution uses the container/heap package, which requires implementing the heap interface manually.

Unlike Python, Go does not provide a built in max heap, so the Less function is reversed to create max heap behavior.

Go slices naturally handle dynamic resizing, making them suitable for heap storage. Since fuel values can reach 10^9, standard int remains safe on LeetCode's 64 bit runtime.

Worked Examples

Example 1

target = 1
startFuel = 1
stations = []

Initial state:

Variable	Value
currentReach	1
heap	[]
refuelStops	0

Since:

currentReach >= target

the loop never executes.

Result:

0

No refueling is required.

Example 2

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

Initial state:

Variable	Value
currentReach	1
heap	[]

The first station is at position 10, which is unreachable.

No stations are added to the heap.

Heap becomes empty before reaching target.

Result:

-1

Example 3

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

Initial state:

Variable	Value
currentReach	10
heap	[]
stops	0

Iteration 1

Reachable stations:

Station	Fuel
10	60

Heap:

[60]

Pop maximum fuel:

currentReach = 10 + 60 = 70
stops = 1

Iteration 2

New reachable stations:

Station	Fuel
20	30
30	30
60	40

Heap:

[40, 30, 30]

Pop maximum fuel:

currentReach = 70 + 40 = 110
stops = 2

Now:

110 >= 100

Result:

2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Each station is pushed and popped from heap at most once
Space	O(n)	Heap may contain all stations

Each station enters the heap exactly once and may be removed once. Heap operations require O(log n) time, producing an overall complexity of O(n log n).

The heap can store up to all reachable stations simultaneously, so the space complexity is linear in the number of stations.

Test Cases

from typing import List

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

        import heapq

        max_heap = []
        current_reach = startFuel
        station_index = 0
        refuel_stops = 0

        while current_reach < target:

            while (
                station_index < len(stations)
                and stations[station_index][0] <= current_reach
            ):
                heapq.heappush(max_heap, -stations[station_index][1])
                station_index += 1

            if not max_heap:
                return -1

            current_reach += -heapq.heappop(max_heap)
            refuel_stops += 1

        return refuel_stops

solution = Solution()

assert solution.minRefuelStops(1, 1, []) == 0
# already enough fuel

assert solution.minRefuelStops(100, 1, [[10, 100]]) == -1
# first station unreachable

assert solution.minRefuelStops(
    100,
    10,
    [[10, 60], [20, 30], [30, 30], [60, 40]]
) == 2
# standard example

assert solution.minRefuelStops(100, 100, []) == 0
# exact fuel to target

assert solution.minRefuelStops(100, 50, []) == -1
# no stations and insufficient fuel

assert solution.minRefuelStops(
    100,
    25,
    [[25, 25], [50, 25], [75, 25]]
) == 3
# exact chain of refuels

assert solution.minRefuelStops(
    100,
    10,
    [[10, 10], [20, 20], [30, 30], [60, 40]]
) == 4
# must use every station

assert solution.minRefuelStops(
    1000,
    299,
    [[13, 21], [26, 115], [100, 47], [225, 99], [299, 141]]
) == 4
# larger distances and greedy selection

assert solution.minRefuelStops(
    100,
    50,
    [[25, 25], [50, 50]]
) == 1
# best to choose largest fuel later

assert solution.minRefuelStops(
    100,
    10,
    [[5, 100]]
) == 1
# reachable early large station

Test Summary

Test	Why
target=1, startFuel=1	Already reachable
startFuel=1, station at 10	Impossible from start
Official example 3	Standard heap behavior
startFuel == target	Exact reach without refueling
No stations and insufficient fuel	Immediate failure
Sequential exact refuels	Multiple mandatory stops
Must use every station	Stress repeated heap usage
Larger distances	Tests greedy correctness
Late larger fuel	Verifies delayed greedy choice
Early large station	Tests immediate beneficial refuel

Edge Cases

One important edge case occurs when the car already has enough fuel to reach the target. A naive implementation might still attempt heap operations or station processing unnecessarily. The current implementation handles this naturally because the main loop only executes while current_reach < target.

Another critical edge case happens when the first gas station is unreachable. In this scenario, no stations can be added to the heap, and the algorithm must correctly return -1. The heap emptiness check guarantees this behavior.

A subtle edge case involves arriving at a station with exactly zero fuel remaining. Some incorrect implementations treat this as failure. However, the problem explicitly allows refueling at zero fuel. The condition:

stations[station_index][0] <= current_reach

correctly includes stations that are reached exactly.

Another tricky situation occurs when several stations are reachable before refueling becomes necessary. A greedy implementation that immediately refuels at the first available station may produce a non optimal answer. The heap based strategy avoids this by delaying decisions until fuel is actually needed, preserving the ability to choose the largest previously reachable station.