#871

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Minimum Number of Refueling Stops

Determine the minimum number of refueling stops needed to reach a target using dynamic programming and greedy strategies with gas stations.

array dynamic programming greedy heap priority queue

Problem Statement

You are driving a car from a starting position to a destination which is target miles east of the start. The car begins with startFuel liters of fuel in an infinite tank and consumes one liter per mile. Along the route, there are gas stations represented as an array stations where stations[i] = [positioni, fueli] indicates a station at positioni miles providing fueli liters.

At each gas station, the car may stop to refuel, taking all the fuel from that station. The goal is to determine the minimum number of refueling stops required to reach the destination. If it is impossible to reach the target, return -1. You must optimize decisions to refuel dynamically based on reachable distances and fuel constraints.

Examples

Example 1

Input: target = 1, startFuel = 1, stations = []

Output: 0

We can reach the target without refueling.

Example 2

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

Output: -1

We can not reach the target (or even the first gas station).

Example 3

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

Output: 2

We start with 10 liters of fuel. We drive to position 10, expending 10 liters of fuel. We refuel from 0 liters to 60 liters of gas. Then, we drive from position 10 to position 60 (expending 50 liters of fuel), and refuel from 10 liters to 50 liters of gas. We then drive to and reach the target. We made 2 refueling stops along the way, so we return 2.

Constraints

1 <= target, startFuel <= 109
0 <= stations.length <= 500
1 <= positioni < positioni+1 < target
1 <= fueli < 109

Solution Approach

Dynamic Programming State Tracking

Use a DP array where dp[i] represents the farthest distance reachable with i refueling stops. Initialize dp[0] = startFuel. For each station, iterate backwards through dp to update maximum reachable distances if refueling at that station improves reach.

Greedy Max-Heap Approach

Maintain a max-heap of fuel amounts from stations you have passed. As long as your current fuel cannot reach the next station or target, pop the largest fuel from the heap and add it to your current fuel. This approach ensures minimal refueling stops.

Combining DP and Greedy Insights

The problem leverages state transition dynamic programming while greedy selection guarantees efficiency. You can precompute reachable distances and selectively refuel using either DP or heap strategies to ensure optimal stopping decisions without redundant computations.

Complexity Analysis

Metric	Value
Time	O(N \log N)
Space	O(N)

Time complexity is O(N \log N) due to heap operations or DP updates for N stations. Space complexity is O(N) to store DP array or heap elements, reflecting fuel choices at each station.

What Interviewers Usually Probe

Asks about edge cases with no stations and minimal start fuel.
Explores the trade-off between DP updates versus greedy max-heap optimization.
Wants explanation on why state transition DP captures minimal refueling stops.

Common Pitfalls or Variants

Common pitfalls

Failing to handle cases where startFuel is enough to reach target without refueling.
Not iterating DP array backwards leading to incorrect state updates.
Using greedy selection without a heap can underestimate required refueling stops.

Follow-up variants

Compute maximum distance reachable with at most K refueling stops.
Determine minimum stops if fuel consumption varies per mile.
Optimize for fuel cost differences at each station instead of quantity.

FAQ

What is the main challenge in Minimum Number of Refueling Stops?

The main challenge is determining at each station whether to refuel, ensuring you reach the target with the fewest stops.

How does the state transition dynamic programming pattern apply here?

DP tracks the maximum distance reachable with i refueling stops, enabling systematic evaluation of minimal refueling sequences.

Can this problem be solved with a purely greedy approach?

A greedy approach with a max-heap works efficiently by always refueling the largest available fuel when necessary, but DP ensures correctness across all configurations.

What should I watch for with edge cases?

Edge cases include no stations, startFuel equal to or greater than target, and unreachable first stations, which require careful handling.

Why use a heap instead of iterating all previous stations each time?

The heap allows selecting the station with maximum fuel efficiently, reducing time complexity from O(N^2) to O(N log N) while maintaining minimal stops.

terminal

Solution

Solution 1: Greedy + Priority Queue (Max-Heap)

We can use a priority queue (max-heap) $\textit{pq}$ to record the fuel amounts of all the gas stations we have passed. Each time the fuel is insufficient, we greedily take out the maximum fuel amount, which is the top element of $\textit{pq}$, and accumulate the number of refuels $\textit{ans}$. If $\textit{pq}$ is empty and the current fuel is still insufficient, it means we cannot reach the destination, and we return $-1$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def minRefuelStops(
        self, target: int, startFuel: int, stations: List[List[int]]
    ) -> int:
        pq = []
        ans = pre = 0
        stations.append([target, 0])
        for pos, fuel in stations:
            dist = pos - pre
            startFuel -= dist
            while startFuel < 0 and pq:
                startFuel -= heappop(pq)
                ans += 1
            if startFuel < 0:
                return -1
            heappush(pq, -fuel)
            pre = pos
        return ans

Continue Practicing

#1388 pizza with 3n slices #857 minimum cost to hire k workers #1024 video stitching