D
DevExCode

LeetCode 871: Minimum Number of Refueling Stops Solution

Master LeetCode problem 871 (Minimum Number of Refueling Stops), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

871. Minimum Number of Refueling Stops

Hard
ArrayDynamic ProgrammingGreedyHeap (Priority Queue)

Problem Explanation

Explanation:

To solve this problem, we can use a priority queue to keep track of the gas stations that we can refuel at. We iterate over the stations and as long as our current fuel is not enough to reach the next station, we refuel from the station with the highest amount of fuel we encountered so far. We keep track of the number of stops we make and return it as the result.

Detailed steps:

  1. Initialize variables: stops = 0 (number of stops), currPos = 0 (current position), currFuel = startFuel.
  2. Initialize a priority queue maxHeap to store the gas stations in descending order of fuel.
  3. Iterate over the gas stations:
    • If we can reach the next station with the current fuel, update currPos and currFuel accordingly.
    • If we can't reach the next station, refuel from the stations in maxHeap until we can reach the next station.
    • If we can't reach the next station even after refueling, return -1.
  4. Return the number of stops made.

Time Complexity: O(n log n) - where n is the number of gas stations. Space Complexity: O(n) - for the priority queue.

:

Solution Code

import java.util.PriorityQueue;

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

        for (int[] station : stations) {
            int stationPos = station[0];
            int stationFuel = station[1];

            while (currFuel < stationPos - currPos) {
                if (maxHeap.isEmpty()) return -1;
                currFuel += maxHeap.poll();
                stops++;
            }

            maxHeap.offer(stationFuel);
            currPos = stationPos;
        }

        while (currFuel < target - currPos) {
            if (maxHeap.isEmpty()) return -1;
            currFuel += maxHeap.poll();
            stops++;
        }

        return stops;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 871 (Minimum Number of Refueling Stops)?

This page provides optimized solutions for LeetCode problem 871 (Minimum Number of Refueling Stops) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 871 (Minimum Number of Refueling Stops)?

The time complexity for LeetCode 871 (Minimum Number of Refueling Stops) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 871 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 871 in Java, C++, or Python.

Back to LeetCode Solutions