Minimum Number of Refueling Stops Hard 0 attempts
LeetCode ↗

Minimum Number of Refueling Stops

Hard HeapPriority Queue LeetCode

A car starts with startFuel and needs to reach target. Gas stations at positions with fuel amounts. Return minimum stops, or -1.

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

Sample Input
—
Sample Output
—
Constraints
  • 1 <= target <= 10^9
  • 0 <= startFuel <= 10^9
  • 0 <= stations.length <= 500
Topics
HeapPriority Queue

Greedy with Max-Heap

As you pass stations, add their fuel to a max-heap. When empty, refuel from the largest available.

function minRefuelStops(target, startFuel, stations) {
  const heap = []; let fuel = startFuel, stops = 0, i = 0;
  while (fuel < target) {
    while (i < stations.length && stations[i][0] <= fuel) heap.push(stations[i++][1]);
    if (!heap.length) return -1;
    heap.sort((a,b) => b-a);
    fuel += heap.shift(); stops++;
  }
  return stops;
}

Time: O(n log n) | Space: O(n)

Saved in this browser only. Private to you.

JavaScript