← Back to Index

📚 Minimum Number of Refueling Stops – Java Cheat Sheet

📌 What Is It?

The Minimum Number of Refueling Stops problem involves finding the minimum number of refueling stops required to reach a target distance with a given starting fuel. You are provided with a list of gas stations, each with a location and fuel capacity.

🧱 Pattern Template

Greedy Algorithm with Max-Heap

class Solution {
    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        int fuel = startFuel, stops = 0, index = 0;

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

            // If no station is reachable and target is not reached, return -1
            if (maxHeap.isEmpty()) return -1;

            // Refuel with the station providing the most fuel
            fuel += maxHeap.poll();
            stops++;
        }

        return stops;
    }
}

▶️ View Animation

📊 Time Complexity

• Heap Operations: O(N log N), where N is the number of stations.
• Total Complexity: O(N log N).

✅ Use Cases

• Optimizing resource usage in constrained environments.
• Solving problems involving cumulative sums and greedy selection.

📘 Common LeetCode Problems

• 871. Minimum Number of Refueling Stops [Hard] Greedy

🧪 Example

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

Explanation:
- Stop at station 0 (10, 60) to refuel. Fuel = 10 + 60 = 70.
- Stop at station 3 (60, 40) to refuel. Fuel = 70 + 40 = 110.
- Reach the target with 2 stops.

💡 Pro Tips

• Use a max-heap to always refuel with the station providing the most fuel.
• Iterate through stations and add them to the heap only if they are reachable.
• If the heap is empty and the target is not reached, return -1.