Problem Description

You are given an integer target, representing the distance to a destination, and an integer startFuel, which is the initial amount of fuel in your car. There are also a list of gas stations, where each station is represented as [position, fuel]: position is the distance from the starting point, and fuel is the amount of fuel that can be refueled at that station.

Your car consumes 1 unit of fuel per mile. You can stop at any station to refuel, but you cannot revisit any station. The goal is to reach the destination using the minimum number of refueling stops. If it is impossible to reach the target, return -1.

• Each station can be used at most once.
• You must not reuse or revisit any station.
• There is always exactly one valid solution or it is impossible (return -1).

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

Thought Process

At first glance, you might think of trying all possible combinations of refueling stops to find the minimum. This brute-force approach quickly becomes infeasible as the number of stations increases. Instead, we should look for a way to always make the optimal choice at each step.

The key insight is to always refuel at the station that gives you the most fuel among all stations you have already passed but not yet used. This is because, whenever you run out of fuel, you want the biggest possible boost to get you as far as possible toward the target.

This naturally leads to a greedy approach, where we keep track of all the stations we could have stopped at, and whenever we need fuel, we pick the one with the largest available fuel. To efficiently find the largest fuel among available stations, we can use a max-heap (priority queue).

Solution Approach

We solve this problem using a greedy algorithm with a max-heap (priority queue). The idea is to always refuel at the station with the most fuel among those we've passed whenever we need more fuel to continue.

1. Initialize variables: Start with startFuel as your current fuel, and zero refueling stops.
2. Iterate over stations (including the target as a final station):
   • For each station, compute the distance from the previous station (or starting point).
   • While your fuel is less than the distance to the next station, refuel from the station with the most fuel among those you've already passed (using the max-heap).
   • If you can't refuel (heap is empty), return -1 (impossible to reach the target).
   • Subtract the distance from your current fuel, then add the current station's fuel to the max-heap (if it's a real station).
3. Return the number of refueling stops used to reach the target.

Why a max-heap? Because we want to always refuel with the largest possible amount among all stations we have passed but not yet used, ensuring we make the most progress.

Example Walkthrough

Let's use the example: target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]

1. Start: Fuel = 10, position = 0, stops = 0, heap = [].
2. First station at position 10:
   • Distance = 10. Fuel (10) is enough. Fuel after move = 0.
   • Add station's fuel (60) to heap. Heap = [60].
3. Second station at position 20:
   • Distance = 10. Fuel (0) is not enough. Refuel from heap (pop 60). Stops = 1, Fuel = 60.
   • Now move: Fuel = 60 - 10 = 50.
   • Add station's fuel (30) to heap. Heap = [30].
4. Third station at position 30:
   • Distance = 10. Fuel (50) is enough. Fuel = 40.
   • Add station's fuel (30) to heap. Heap = [30, 30].
5. Fourth station at position 60:
   • Distance = 30. Fuel (40) is enough. Fuel = 10.
   • Add station's fuel (40) to heap. Heap = [40, 30, 30].
6. Destination at position 100:
   • Distance = 40. Fuel (10) is not enough. Refuel from heap (pop 40). Stops = 2, Fuel = 50.
   • Now move: Fuel = 50 - 40 = 10.
   • Reached target. Total stops = 2.

Time and Space Complexity

• Brute-force approach: Try all combinations of stops (exponential, O(2^n)), which is infeasible for large n.
• Optimized (Heap-based) approach:
  • Time Complexity: O(n log n), where n is the number of stations. For each station, we may push/pop from the heap, which takes log n time.
  • Space Complexity: O(n), as in the worst case, all stations' fuel amounts are stored in the heap.

Summary

The Minimum Number of Refueling Stops problem can be solved efficiently using a greedy algorithm and a max-heap. By always choosing to refuel at the station with the most fuel among those we've passed, we ensure we make maximum progress toward the target with the fewest stops. The approach is both optimal and efficient, reducing the time complexity from exponential (brute-force) to O(n log n) using a priority queue.

Code Implementation

import heapq

class Solution:
    def minRefuelStops(self, target, startFuel, stations):
        heap = []
        stations.append([target, 0])
        prev = 0
        fuel = startFuel
        stops = 0

        for pos, cap in stations:
            fuel -= (pos - prev)
            while heap and fuel < 0:
                fuel += -heapq.heappop(heap)
                stops += 1
            if fuel < 0:
                return -1
            heapq.heappush(heap, -cap)
            prev = pos
        return stops
      

#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
        priority_queue<int> pq;
        stations.push_back({target, 0});
        int prev = 0, fuel = startFuel, stops = 0;
        for (const auto& station : stations) {
            int pos = station[0], cap = station[1];
            fuel -= (pos - prev);
            while (!pq.empty() && fuel < 0) {
                fuel += pq.top();
                pq.pop();
                stops++;
            }
            if (fuel < 0)
                return -1;
            pq.push(cap);
            prev = pos;
        }
        return stops;
    }
};
      

import java.util.*;

class Solution {
    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        int prev = 0, fuel = startFuel, stops = 0;
        int n = stations.length;
        int i = 0;
        while (fuel < target) {
            while (i < n && stations[i][0] <= prev + fuel) {
                pq.offer(stations[i][1]);
                i++;
            }
            if (pq.isEmpty()) return -1;
            fuel += pq.poll();
            stops++;
            prev = fuel + prev - pq.peek();
        }
        return stops;
    }
}
      

/**
 * @param {number} target
 * @param {number} startFuel
 * @param {number[][]} stations
 * @return {number}
 */
var minRefuelStops = function(target, startFuel, stations) {
    let heap = [];
    let prev = 0, fuel = startFuel, stops = 0;
    stations.push([target, 0]);

    for (let [pos, cap] of stations) {
        fuel -= (pos - prev);
        while (heap.length > 0 && fuel < 0) {
            fuel += heap.pop();
            stops++;
        }
        if (fuel < 0) return -1;
        // Insert in sorted order (max-heap)
        let idx = heap.findIndex(x => x < cap);
        if (idx === -1) heap.push(cap);
        else heap.splice(idx, 0, cap);
        prev = pos;
    }
    return stops;
};