# Minimum Number of Refueling Stops
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-number-of-refueling-stops)
Canonical: https://scaleengineer.com/dsa/problems/minimum-number-of-refueling-stops
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array, Heap (Priority Queue)
**Companies:** [Barclays](https://scaleengineer.com/companies/barclays), [Flipkart](https://scaleengineer.com/companies/flipkart), [Morgan Stanley](https://scaleengineer.com/companies/morgan-stanley), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [Snap](https://scaleengineer.com/companies/snap), [Rubrik](https://scaleengineer.com/companies/rubrik)
---
## Problem
A car travels from a starting position to a destination which is `target` miles east of the starting position.

There are gas stations along the way. The gas stations are represented as an array `stations` where `stations[i] = [positioni, fueli]` indicates that the `ith` gas station is `positioni` miles east of the starting position and has `fueli` liters of gas.

The car starts with an infinite tank of gas, which initially has `startFuel` liters of fuel in it. It uses one liter of gas per one mile that it drives. When the car reaches a gas station, it may stop and refuel, transferring all the gas from the station into the car.

Return _the minimum number of refueling stops the car must make in order to reach its destination_. If it cannot reach the destination, return `-1`.

Note that if the car reaches a gas station with `0` fuel left, the car can still refuel there. If the car reaches the destination with `0` fuel left, it is still considered to have arrived.

**Example 1:**

**Input:** target = 1, startFuel = 1, stations = []
**Output:** 0
**Explanation:** We can reach the target without refueling.

**Example 2:**

**Input:** target = 100, startFuel = 1, stations = [[10,100]]
**Output:** -1
**Explanation:** 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
**Explanation:** 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`

# Approaches
## Dynamic Programming
This approach uses dynamic programming to solve the problem. We define `dp[i]` as the maximum distance one can reach from the starting point by making exactly `i` refueling stops. Our goal is to find the smallest `i` for which `dp[i]` is greater than or equal to the `target` distance.
**Time:** O(N^2), where N is the number of stations. We have two nested loops, each iterating up to N. · **Space:** O(N), where N is the number of stations, to store the `dp` array.
**Pros:** The DP state and transition are logical and relatively easy to formulate.; It correctly solves the problem for the given constraints.
**Cons:** The O(N^2) time complexity is less efficient than the greedy approach, which can be a drawback for larger N.
### Explanation
We initialize a `dp` array of size `n+1`, where `n` is the number of gas stations. `dp[i]` will store the furthest reachable distance with `i` stops. `dp[0]` is initialized to `startFuel`, as this is the maximum distance we can travel without any stops. We then iterate through each gas station `s`. For each station, we consider the possibility of making it a refueling stop by iterating backwards through the number of stops `j`. We iterate backwards to ensure that we use each station at most once for a given number of stops. If our current maximum reach with `j` stops, `dp[j]`, is enough to get to the current station `s` (i.e., `dp[j] >= s.position`), we can potentially make this our `(j+1)`-th stop. By refueling, our new maximum reach with `j+1` stops would be `dp[j] + s.fuel`. We update `dp[j+1]` to be the maximum of its current value and this new potential reach. After processing all stations, we find the first index `i` where `dp[i] >= target`. This `i` is our answer. If no such `i` exists, we return -1. We use a `long` type for the `dp` array to prevent potential integer overflows with large fuel and target values.

```java
public int minRefuelStops(int target, int startFuel, int[][] stations) {
    int n = stations.length;
    long[] dp = new long[n + 1];
    dp[0] = startFuel;

    for (int i = 0; i < n; i++) {
        int position = stations[i][0];
        int fuel = stations[i][1];
        for (int j = i; j >= 0; j--) {
            if (dp[j] >= position) {
                dp[j + 1] = Math.max(dp[j + 1], dp[j] + fuel);
            }
        }
    }

    for (int i = 0; i <= n; i++) {
        if (dp[i] >= target) {
            return i;
        }
    }

    return -1;
}
```
### Algorithm
- Let `n` be the number of stations.
- Create a `long` array `dp` of size `n + 1`. `dp[i]` will store the maximum distance reachable with `i` stops.
- Initialize `dp[0] = startFuel`. All other `dp` entries are initialized to 0.
- Iterate through each station `s` from `i = 0` to `n-1`:
  - For each number of stops `j` from `i` down to `0`:
    - If `dp[j]` is greater than or equal to the position of station `i`, it means we can reach this station with `j` stops.
    - We can potentially refuel here, making it our `(j+1)`-th stop. The new maximum reach would be `dp[j] + s.fuel`.
    - Update `dp[j+1] = max(dp[j+1], dp[j] + s.fuel)`.
- After iterating through all stations, find the smallest `i` such that `dp[i] >= target`.
- If no such `i` exists, it's impossible to reach the target, so return -1.

## Greedy Approach with Max-Heap
A more efficient approach is a greedy one. The core idea is to drive as far as possible with the current fuel. When we can no longer proceed, we must refuel. To maximize our travel distance, we should retroactively use the fuel from a station we have already passed that had the largest amount of fuel. A max-heap is the perfect data structure to efficiently find this largest fuel amount among the reachable stations.
**Time:** O(N log N), where N is the number of stations. Each station is pushed onto the heap once (O(log N)) and popped at most once (O(log N)). · **Space:** O(N), where N is the number of stations, to store the fuel of all stations in the max-heap in the worst case.
**Pros:** More efficient time complexity than the DP approach.; The logic of "drive as far as you can, then refuel with the best option" is an elegant and powerful greedy paradigm.
**Cons:** The correctness of the greedy choice might be less obvious to prove compared to the DP formulation.
### Explanation
We simulate the car's journey by keeping track of the maximum distance we can reach, `currentReach`, which starts at `startFuel`. We also use a max-heap (implemented as a `PriorityQueue` in Java) to store the fuel from stations we have passed. We iterate as long as our `currentReach` is less than the `target`. In each step of the main loop, we first add all newly reachable stations to our max-heap. A station is reachable if its position is less than or equal to our `currentReach`. After adding all such stations, we check if we've reached the target. If not, we must refuel. We do this by taking the largest fuel amount from the heap (which corresponds to the best refueling option among the stations we've passed), add it to our `currentReach`, and increment our stop count. If the heap is empty and we still haven't reached the target, it means we are stranded and cannot proceed, so we return -1. This process continues until we can reach the target, at which point we return the number of stops made.

```java
import java.util.Collections;
import java.util.PriorityQueue;

public int minRefuelStops(int target, int startFuel, int[][] stations) {
    if (startFuel >= target) {
        return 0;
    }
    
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    int stops = 0;
    long currentReach = startFuel;
    int stationIndex = 0;
    int n = stations.length;

    while (currentReach < target) {
        // Add all reachable stations' fuel to the max-heap
        while (stationIndex < n && stations[stationIndex][0] <= currentReach) {
            maxHeap.offer(stations[stationIndex][1]);
            stationIndex++;
        }

        // If we can't reach further and no stations to refuel from, it's impossible
        if (maxHeap.isEmpty()) {
            return -1;
        }

        // Refuel from the station with the most fuel among those we've passed
        currentReach += maxHeap.poll();
        stops++;
    }

    return stops;
}
```
### Algorithm
- Initialize `stops = 0`, `currentReach = startFuel`, and `stationIndex = 0`.
- Create a max-heap `pq` to store fuel from passed stations.
- Loop as long as `currentReach < target`:
  - Add the fuel of all stations that are currently reachable (`station.position <= currentReach`) to the `pq`.
  - If `currentReach` is still less than `target`, we must refuel.
  - If `pq` is empty at this point, it's impossible to proceed. Return -1.
  - Pop the largest fuel amount from `pq`, add it to `currentReach`, and increment `stops`.
- Once `currentReach >= target`, the loop terminates. Return the total `stops`.

# Solutions
### Java

```java
class Solution {
public
  int minRefuelStops(int target, int startFuel, int[][] stations) {
    PriorityQueue<Integer> q = new PriorityQueue<>((a, b)->b - a);
    int n = stations.length;
    int prev = 0, ans = 0;
    for (int i = 0; i < n + 1; ++i) {
      int d = (i < n ? stations[i][0] : target) - prev;
      startFuel -= d;
      while (startFuel < 0 && !q.isEmpty()) {
        startFuel += q.poll();
        ++ans;
      }
      if (startFuel < 0) {
        return -1;
      }
      if (i < n) {
        q.offer(stations[i][1]);
        prev = stations[i][0];
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minRefuelStops(int target, int startFuel, vector<vector<int>> &stations) {
    priority_queue<int> q;
    stations.push_back({target, 0});
    int ans = 0, prev = 0;
    for (auto &s : stations) {
      int d = s[0] - prev;
      startFuel -= d;
      while (startFuel < 0 && !q.empty()) {
        startFuel += q.top();
        q.pop();
        ++ans;
      }
      if (startFuel < 0)
        return -1;
      q.push(s[1]);
      prev = s[0];
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int: q = [] prev = ans = 0 stations . append([target, 0]) for a, b in stations: d = a - prev startFuel -= d while startFuel < 0 and q: startFuel -= heappop(q) ans += 1 if startFuel < 0: return - 1 heappush(q, - b) prev = a return ans

```