AlgoMaster Logo

Minimum Number of Refueling Stops

hardFrequency8 min readUpdated June 23, 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.

Stopping at more stations gives more fuel and more range, but the goal is to minimize stops. So we have to choose which stations to use carefully. Stations are not equally valuable: one offering 100 liters extends our range far more than one offering 5 liters. Preferring stations with the most fuel is what drives 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.
  • stations is sorted by position → No need to sort. We can process stations left to right.

Approach 1: Brute Force (Try All Subsets)

Intuition

Try every possible subset of stations to stop at, and for each subset check whether the car can reach the target. Among all subsets that reach the target, keep the one with the fewest stations.

Each station is either used or skipped, giving 2^n subsets. A DFS with backtracking explores these: at each station we branch on stopping (gain its fuel) or skipping it. Two prunes cut the search. If we cannot reach the current station with our remaining fuel, every later station is also unreachable on this branch (positions are sorted), so we stop. And if we already found a solution with k stops, any branch that has already used k or more stops cannot improve the answer.

This is correct but exponential, so it is unusable once n grows past roughly 20.

Algorithm

  1. Start a DFS from position 0 with startFuel and 0 stops.
  2. At each station, check if we have enough fuel to reach it. If not, prune this branch.
  3. If we can reach the target from our current position, update the best answer.
  4. Try two choices: stop at the next station (gain fuel) or skip it.
  5. Track the minimum number of stops across all valid paths.

Example Walkthrough

The DFS explores a branching tree of stop/skip decisions, which does not map cleanly onto a linear animation, so there is no animated trace here. The Dynamic Programming approach below includes a full step-by-step walkthrough on the same input.

Code

The exponential cost makes this impractical for large inputs. The next approach replaces the subset search with a compact table that tracks the farthest position reachable for each number of stops.

Approach 2: Dynamic Programming

Intuition

Instead of exploring all subsets, define a state that summarizes what each stop count buys. Let dp[k] be the farthest position reachable 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.

Iterating k from i down to 0 matters because each station can be used at most once. Updating dp[k+1] from dp[k] while moving k downward reads each dp[k] before this station has modified it, so a single station never gets folded into the same path twice. This is the in-place update order from the 0/1 knapsack.

Tracking only the farthest reachable position per stop count is enough because reaching farther is never worse: if dp[k] reaches position p, then with k stops we can reach any station at a position less than or equal to p, so a larger dp[k] dominates a smaller one and we only need to keep the maximum.

Algorithm

  1. Create array dp of size n+1, initialized to 0. Set dp[0] = startFuel.
  2. For each station i (from 0 to n-1):
    • For k from i down to 0:
      • If dp[k] >= stations[i][0] (we can reach this station with k stops), update dp[k+1] = max(dp[k+1], dp[k] + stations[i][1]).
  3. Return the smallest k where dp[k] >= target. If none exists, return -1.

Example Walkthrough

1Initial: dp[0]=startFuel=10, dp[1..4]=0 (unreachable)
0
10
10 mi
1
0
2
0
3
0
4
0
1/6

Code

The DP is polynomial, but its inner loop revisits every (station, stop-count) pair. The next approach defers each stop decision until the moment fuel actually runs out, which removes that inner loop.

Approach 3: Greedy with Max-Heap (Optimal)

Intuition

Refueling decisions can be deferred until they are forced. Drive forward and pass stations without committing to any of them. When fuel runs out before the next waypoint, a stop is now mandatory, and the best station to charge that stop to is the one with the most fuel among all stations already passed. Its position no longer matters, since the car has driven beyond it either way, so the choice can be made retroactively.

This turns into a single forward pass backed by a max-heap. Every time the car passes a station, push that station's fuel onto the heap. Before reaching the next waypoint (the next station, or the target as the final waypoint), if the running fuel has gone negative, pop the largest fuel value and add it to the tank, counting one stop. Repeat until fuel is non-negative. If the heap empties and fuel is still negative, the target is unreachable, so return -1.

Algorithm

  1. Initialize fuel = startFuel, stops = 0, prevPosition = 0, and a max-heap.
  2. For each station (and the target as a final waypoint):
    • Subtract the distance traveled: fuel -= (station.position - prevPosition).
    • While fuel < 0 and the heap is not empty: pop the largest fuel from the heap, add it to fuel, increment stops.
    • If fuel < 0 and the heap is empty, return -1 (impossible to reach).
    • Push this station's fuel onto the heap.
    • Update prevPosition = station.position.
  3. Return stops.

Example Walkthrough

stations
1Start: fuel=10, stops=0. Drive toward station at pos=10.
0
10
next
1
20
2
30
3
60
4
100
maxHeap
1Heap empty. Starting drive.
[]
1/6

Code