Minimum Number of Refueling Stops — Understanding Greedy + Max Heap

Harsh Jaiswal

5 min read

·

Oct 26, 2026

--

Listen

Share

Introduction

Today, I solved LeetCode 871 — Minimum Number of Refueling Stops, and it helped me understand how Greedy Algorithms and Heaps work together to solve an optimization problem.

At first, the problem looks like a simple journey-planning question. However, the real challenge is deciding when to refuel and which station’s fuel to choose so that we reach our destination with the minimum number of stops.

Let’s break down the intuition, algorithm, and implementation.

1. Understanding the Problem

Imagine that you are driving a car toward a destination.

You are given:

• target: The distance to your destination.
• startFuel: The amount of fuel available initially.
• stations: An array where each station contains its position and the amount of fuel it provides.

Your task is to reach the destination using the minimum possible number of refueling stops.

For example:

target = 100;
startFuel = 10;

stations = {
    {10, 60},
    {20, 30},
    {30, 30},
    {60, 40}
};

Each pair represents {position, fuel}.

For example, {10, 60} means a petrol station is located 10 units from the starting point and provides 60 units of fuel.

The answer is 2, because we can reach the destination with only two refueling stops.

2. Real-Life Analogy: Planning a Long Road Trip

Imagine you are driving a car with limited fuel.

You encounter several petrol stations along the highway. Some provide 20 litres, some provide 40 litres, and others provide 60 litres.

Would you stop at every petrol station?

Not necessarily!

Instead, you can keep moving while your current fuel is sufficient. If you later discover that you cannot reach the next destination, you can use the fuel available from a station you have already passed.

The smart strategy is to choose the station that provides the maximum available fuel.

This is the intuition behind combining Greedy and Max Heap.

3. Why Do We Need a Greedy Algorithm?

A Greedy Algorithm makes a locally optimal choice at each step in the hope of achieving a globally optimal solution.

In this problem, we want to minimize the number of refueling stops.

Whenever our fuel becomes insufficient, we choose the largest available fuel amount from the stations we have already reached.

Why?

Because a larger fuel amount can help us travel farther with the same number of stops.

We do not refuel unnecessarily at every station. Instead, we postpone the decision until additional fuel is needed.

Important: We only consider stations that we can reach. We cannot use fuel from a station that is still ahead of us.

4. Why Do We Need a Max Heap?

A Max Heap allows us to retrieve the largest available fuel amount efficiently.

In C++, the default priority_queue<int> is a Max Heap.

priority_queue<int> pq;

pq.push(60);
pq.push(30);
pq.push(40);

Now:

pq.top();  // 60

The largest value is always available at the top.

The key operations are:

• pq.push(fuel): Add fuel from a reachable station.
• pq.top(): Access the largest available fuel amount.
• pq.pop(): Remove that amount after using it.

Both insertion and removal take (O(\log n)) time, while accessing the top takes (O(1)) time.

The heap helps us avoid repeatedly searching through all previously reached stations to find the one with the most fuel.

Press enter or click to view image in full size

Understanding the Important Variables

fuel — Current available fuel

It tracks how much fuel remains after travelling to the current position.

prev — Previous position

It helps calculate the distance travelled between consecutive stations.

pq — Max Heap

It stores the fuel amounts of stations we have already reached but have not yet selected for refueling.

ans — Number of refueling stops

It increases only when we actually take fuel from the heap.

The Most Important Logic

Step 1: Calculate the distance

fuel -= (pos - prev);

Suppose the previous position is 20 and the next position is 60.

The distance travelled is:

[
60–20 = 40
]

If we had 50 units of fuel, we would have 10 remaining.

Step 2: Check whether the fuel is negative

while (fuel < 0)

Negative fuel means that our current fuel is insufficient to reach the current position.

We must refuel before proceeding.

Step 3: Choose the maximum available fuel

if (pq.empty()) {
    return -1;
}

fuel += pq.top();
pq.pop();
ans++;

If the heap is empty, no previously reached station can provide additional fuel, so the destination is unreachable.

Otherwise, we take the maximum available fuel, remove it from the heap, and increment our stop count.

The while loop is important because we may need more than one previously available station's fuel to reach the current position.

Step 4: Add the current station

if (i < stations.size()) {
    pq.push(stations[i][1]);
}

Once we reach a station, its fuel becomes available for future use.

Notice that adding fuel to the heap does not mean that we have refueled. It only means that the station is now an available option.

We count a stop only when we take its fuel from the heap.

Dry Run

Consider the same example:

target = 100;
startFuel = 10;

stations = {
    {10, 60},
    {20, 30},
    {30, 30},
    {60, 40}
};

At the destination, the remaining fuel is:

[
10–40 + 40 = 10
]

We successfully reach the destination with 2 refueling stops.

9. Time and Space Complexity

Let (n) be the number of fuel stations.

Time Complexity: (O(n\log n))

Each station’s fuel is inserted into the heap at most once and removed at most once. Each heap insertion or removal takes (O(\log n)) time.

Space Complexity: (O(n))

In the worst case, the heap can contain fuel amounts from all (n) stations.

10. What I Learned Today

Solving this problem strengthened my understanding of three important ideas:

1. Greedy: Make a strategic choice when additional fuel is required.
2. Max Heap: Efficiently select the largest available fuel amount.
3. Delayed decision-making: Keep available options in the heap and commit to a refueling stop only when necessary.

The most important lesson is that a heap is not just a data structure for finding maximum or minimum values. When combined with a greedy strategy, it can help solve optimization problems efficiently.

Conclusion

LeetCode 871 was a great exercise in understanding how two concepts can work together to produce an efficient solution.

My key takeaway:

Greedy decides when a choice is necessary, and the Max Heap helps us choose the best available option.

👋 Connect with Me:
🔎LEETCODE :- https://leetcode.com/u/HARSHJAISWAL2707/

👤LinkedIn :- https://www.linkedin.com/in/mr-harsh-jaiswal-76691a32a/

Written by Mr. Harsh Jaiswal — B.Tech CSE | DSA & Web Development

#HeapWithGreedy #RefuelingStops #DSA #CodingInterview #EnjoyProblems