Minimum Number of Refueling Stops
Last Updated: March 29, 2026
Understanding the Problem
We are driving a car from position 0 to position target. The car burns exactly 1 liter per mile, so "fuel" and "distance" are interchangeable. We begin with startFuel liters, meaning we can initially travel startFuel miles without stopping. Along the route there are gas stations at fixed positions, each offering a specific amount of fuel. We need to find the minimum number of stops required to reach the destination, or return -1 if it is impossible.
The key tension here is that stopping at more stations gives us more fuel (more range), but we want to minimize the number of stops. So we need to be strategic about which stations to stop at. Not all stations are equally valuable. A station offering 100 liters of fuel is much more useful than one offering 5 liters. This observation, that we should prefer stations with the most fuel, is what guides us toward the optimal solution.
Key Constraints:
0 <= stations.length <= 500→ With at most 500 stations, an O(n^2) DP solution is very comfortable. Even O(n^2 log n) would work fine.1 <= target, startFuel <= 10^9→ These values are huge, so we cannot simulate mile-by-mile. We need to work with station positions directly.stationsis sorted by position → No need to sort. We can process stations left to right.
Approach 1: Brute Force (Try All Subsets)
Intuition
The most direct approach: try every possible subset of stations to stop at, and for each valid subset, check whether the car can reach the target. Among all valid subsets, return the one with the fewest stations.
Each station is either visited or skipped, giving us 2^n possible subsets. We can implement this with DFS/backtracking. At each station, we decide whether to stop there. If we stop, we gain its fuel. If we skip it, we just drive past. We prune branches early: if we cannot even reach the current station, there is no point exploring further. And if we already found a solution with k stops, any branch with k or more stops so far can be abandoned.
This is the natural first thought. It is correct, but extremely slow for large inputs.
Algorithm
- Start a DFS from position 0 with
startFueland 0 stops. - At each station, check if we have enough fuel to reach it. If not, prune this branch.
- If we can reach the target from our current position, update the best answer.
- Try two choices: stop at the next station (gain fuel) or skip it.
- Track the minimum number of stops across all valid paths.
Example Walkthrough
There is no animated walkthrough for this brute force approach since the DFS tree is branching and hard to visualize in a linear animation. See Approach 2 for a detailed step-by-step walkthrough.
Code
- Time Complexity: O(2^n). In the worst case, we explore all subsets of stations. Pruning helps in practice but does not change the worst-case bound.
- Space Complexity: O(n). The recursion depth is at most n (one call per station).
The exponential blowup makes this impractical for large inputs. What if we could summarize "the farthest I can reach with exactly k stops" and build that up incrementally?
Approach 2: Dynamic Programming
Intuition
Instead of exploring all subsets, let us define a state that captures the essential information. Define dp[k] as the farthest position we can reach using exactly k refueling stops. Initially, dp[0] = startFuel (we can reach startFuel miles with zero stops), and all other entries are 0 (meaning unreachable).
Now, process each station one by one (left to right). For station i at position stations[i][0] with fuel stations[i][1], we ask: for each number of stops k from i down to 0, if dp[k] >= stations[i][0] (meaning we can reach this station with k stops), then by stopping here we can extend our range to dp[k] + stations[i][1] using k+1 stops. So we update dp[k+1] = max(dp[k+1], dp[k] + stations[i][1]).
After processing all stations, we scan dp[0], dp[1], dp[2], ... and return the first k where dp[k] >= target. This is the minimum number of stops needed.
Why iterate k from i down to 0? Because we process stations left to right and each station can be used at most once. By going backwards, we ensure we do not "use" the same station twice in a single update pass. This is the same trick used in the 0/1 knapsack problem.
The DP works because it captures the essential trade-off: with more stops, you can reach farther. The dp[k] array compactly represents the best outcome for each possible number of stops. Processing stations left to right and iterating stops backwards ensures each station is counted at most once, just like the 0/1 knapsack. The "farthest reachable position" is the right metric because if you can reach farther, you can always choose to stop at any station along the way.
Algorithm
- Create array
dpof sizen+1, initialized to 0. Setdp[0] = startFuel. - For each station
i(from 0 to n-1): - For
kfromidown to0: - If
dp[k] >= stations[i][0](we can reach this station with k stops), updatedp[k+1] = max(dp[k+1], dp[k] + stations[i][1]). - Return the smallest
kwheredp[k] >= target. If none exists, return -1.
Example Walkthrough
Code
- Time Complexity: O(n^2). For each of the n stations, we iterate over up to n values of k.
- Space Complexity: O(n). The dp array has n+1 entries.
The DP approach is polynomial but its inner loop considers every (station, stop-count) pair. Can we avoid that by making stop decisions lazily, only when we are forced to?
Approach 3: Greedy with Max-Heap (Optimal)
Intuition
Here is the key greedy insight: imagine you are driving along and you pass several gas stations without stopping. At some point, you run out of fuel and cannot reach the next station (or the target). Now you need to refuel. Which station should you have stopped at? The one that gives the most fuel, of course. It does not matter where that station was, because you already passed it. You can "retroactively" decide to have stopped there.
This leads to a beautiful algorithm. Drive forward, and every time you pass a station, toss its fuel value into a max-heap. When you cannot reach the next waypoint (the next station or the target), pop the largest fuel value from the heap and add it to your tank. Each pop represents one refueling stop. If the heap is empty and you still cannot reach the next point, return -1.
The greedy choice is provably optimal via an exchange argument. Suppose there is an optimal solution that stops at station A (with fuel a) but not station B (with fuel b > a), where both were reachable. We can swap: stop at B instead of A. Since b > a, we have at least as much fuel at every point after the swap, so we can still reach every subsequent station and the target. The number of stops stays the same, but we never need more fuel. This means the greedy approach of always picking the largest available fuel can match or beat any other strategy with the same number of stops.
Algorithm
- Initialize
fuel = startFuel,stops = 0,prevPosition = 0, and a max-heap. - For each station (and the target as a final waypoint):
- Subtract the distance traveled:
fuel -= (station.position - prevPosition). - While
fuel < 0and the heap is not empty: pop the largest fuel from the heap, add it tofuel, incrementstops. - If
fuel < 0and the heap is empty, return -1 (impossible to reach). - Push this station's fuel onto the heap.
- Update
prevPosition = station.position. - Return
stops.
Example Walkthrough
Code
- Time Complexity: O(n log n). We process each station once. Each station's fuel is pushed to and popped from the heap at most once, and each heap operation is O(log n).
- Space Complexity: O(n). The heap can hold at most n elements (one per station).