Minimum Number of Refueling Stops

Find minimum refueling stops to reach target using greedy max-heap approach

Language Selection

Choose your preferred programming language

Showing: Python

Minimum Number of Refueling Stops

Problem Statement

A car travels from a starting position to a destination which is target miles east of the starting position.

There are gas stations along the way. The gas stations are represented as an array stations where stations[i] = [position_i, fuel_i] indicates that the ith gas station is position_i miles east of the starting position and has fuel_i liters of gas.

The car starts with an infinite tank and startFuel liters of gas. It uses 1 liter of gas per 1 mile. When the car reaches a gas station, it may stop and refuel, obtaining all the gas from that station.

Return the minimum number of refueling stops the car must make in order to reach its destination. If it cannot reach the destination, return -1.

Input/Output Specifications

  • Input:
    • target: Integer representing target distance
    • startFuel: Integer representing initial fuel
    • stations: Array where each element is [position, fuel]
  • Output: Integer representing minimum refueling stops, or -1 if impossible

Constraints

  • 1 <= target, startFuel <= 10^9
  • 0 <= stations.length <= 500
  • 0 <= position_i <= position_{i+1} < target
  • 1 <= fuel_i < 10^9

Examples

Example 1:

Input: target = 1, startFuel = 1, stations = []
Output: 0
Explanation: We can reach the target without refueling.

Example 2:

Input: target = 100, startFuel = 1, stations = [[10,100]]
Output: -1
Explanation: We can't reach or pass the first gas station.

Example 3:

Input: target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
Output: 2
Explanation: 
Start with 10 liters. Drive to position 10 and refuel (fuel = 60).
Drive to position 60 and refuel (fuel = 40). Now we can reach position 100.

Solution Approaches

Approach 1: Greedy with Max-Heap (Optimal)

Algorithm Explanation:

  1. Use greedy strategy: when running out of fuel, refuel at the station with maximum fuel among passed stations
  2. Use max-heap to track fuel amounts of passed stations
  3. For each position:
    • Add reachable stations to heap
    • If can’t reach target, refuel from best station (max fuel)
    • Continue until target is reached or impossible

Implementation:

Python:

import heapq

def min_refuel_stops(target, startFuel, stations):
    """
    Find minimum refueling stops using greedy max-heap approach
    Time: O(n log n)
    Space: O(n)
    """
    if startFuel >= target:
        return 0
    
    max_heap = []  # Max-heap of fuel amounts (use negative values)
    fuel = startFuel
    position = 0
    stops = 0
    i = 0
    
    while fuel < target:
        # Add all reachable stations to heap
        while i < len(stations) and stations[i][0] <= fuel:
            heapq.heappush(max_heap, -stations[i][1])  # Negative for max-heap
            i += 1
        
        # If no stations available, impossible to reach target
        if not max_heap:
            return -1
        
        # Refuel at station with maximum fuel
        max_fuel = -heapq.heappop(max_heap)
        fuel += max_fuel
        stops += 1
    
    return stops

# Alternative implementation with clearer logic
def min_refuel_stops_v2(target, startFuel, stations):
    """
    Alternative implementation with explicit position tracking
    Time: O(n log n)
    Space: O(n)
    """
    heap = []  # Max heap of fuel amounts
    fuel = startFuel
    stops = 0
    i = 0
    
    while fuel < target:
        # Collect all stations within current fuel range
        while i < len(stations) and stations[i][0] <= fuel:
            heapq.heappush(heap, -stations[i][1])
            i += 1
        
        if not heap:
            return -1  # No stations reachable
        
        # Use the station with maximum fuel
        fuel += -heapq.heappop(heap)
        stops += 1
    
    return stops

Java:

import java.util.*;

class Solution {
    /**
     * Find minimum refueling stops using greedy max-heap
     * Time: O(n log n)
     * Space: O(n)
     */
    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        if (startFuel >= target) return 0;
        
        // Max heap for fuel amounts
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        
        int fuel = startFuel;
        int stops = 0;
        int i = 0;
        
        while (fuel < target) {
            // Add all reachable stations to heap
            while (i < stations.length && stations[i][0] <= fuel) {
                maxHeap.offer(stations[i][1]);
                i++;
            }
            
            // If no stations available
            if (maxHeap.isEmpty()) {
                return -1;
            }
            
            // Refuel at station with maximum fuel
            fuel += maxHeap.poll();
            stops++;
        }
        
        return stops;
    }
}

Go:

import (
    "container/heap"
)

type MaxHeap []int

func (h MaxHeap) Len() int           { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h MaxHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MaxHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *MaxHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

// minRefuelStops - Find minimum refueling stops using max-heap
// Time: O(n log n), Space: O(n)
func minRefuelStops(target int, startFuel int, stations [][]int) int {
    if startFuel >= target {
        return 0
    }
    
    maxHeap := &MaxHeap{}
    heap.Init(maxHeap)
    
    fuel := startFuel
    stops := 0
    i := 0
    
    for fuel < target {
        // Add reachable stations
        for i < len(stations) && stations[i][0] <= fuel {
            heap.Push(maxHeap, stations[i][1])
            i++
        }
        
        if maxHeap.Len() == 0 {
            return -1
        }
        
        // Refuel at best station
        fuel += heap.Pop(maxHeap).(int)
        stops++
    }
    
    return stops
}

JavaScript:

class MaxHeap {
    constructor() {
        this.heap = [];
    }
    
    push(val) {
        this.heap.push(val);
        this.bubbleUp();
    }
    
    pop() {
        if (this.heap.length === 0) return null;
        if (this.heap.length === 1) return this.heap.pop();
        
        const max = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.bubbleDown();
        return max;
    }
    
    size() {
        return this.heap.length;
    }
    
    bubbleUp() {
        let idx = this.heap.length - 1;
        while (idx > 0) {
            const parentIdx = Math.floor((idx - 1) / 2);
            if (this.heap[parentIdx] >= this.heap[idx]) break;
            [this.heap[parentIdx], this.heap[idx]] = [this.heap[idx], this.heap[parentIdx]];
            idx = parentIdx;
        }
    }
    
    bubbleDown() {
        let idx = 0;
        while (2 * idx + 1 < this.heap.length) {
            let maxChildIdx = 2 * idx + 1;
            if (2 * idx + 2 < this.heap.length && 
                this.heap[2 * idx + 2] > this.heap[maxChildIdx]) {
                maxChildIdx = 2 * idx + 2;
            }
            
            if (this.heap[idx] >= this.heap[maxChildIdx]) break;
            [this.heap[idx], this.heap[maxChildIdx]] = [this.heap[maxChildIdx], this.heap[idx]];
            idx = maxChildIdx;
        }
    }
}

/**
 * Find minimum refueling stops using greedy max-heap
 * Time: O(n log n)
 * Space: O(n)
 */
function minRefuelStops(target, startFuel, stations) {
    if (startFuel >= target) return 0;
    
    const maxHeap = new MaxHeap();
    let fuel = startFuel;
    let stops = 0;
    let i = 0;
    
    while (fuel < target) {
        // Add all reachable stations
        while (i < stations.length && stations[i][0] <= fuel) {
            maxHeap.push(stations[i][1]);
            i++;
        }
        
        if (maxHeap.size() === 0) {
            return -1;
        }
        
        // Refuel at best station
        fuel += maxHeap.pop();
        stops++;
    }
    
    return stops;
}

Key Insights

  • Greedy Strategy: When fuel runs low, always choose the station with maximum fuel among reachable stations
  • Retroactive Decision: Can “retroactively” decide which stations to use
  • Max-Heap Usage: Efficiently track and select best fuel option
  • Reachability: Only consider stations within current fuel range

Edge Cases

  1. No Refueling Needed: startFuel >= target
  2. Impossible Journey: No reachable stations or insufficient total fuel
  3. Empty Stations: No gas stations available
  4. Single Station: Only one station to consider
  5. All Stations Same Position: Multiple stations at same location

Test Cases

def test_min_refuel_stops():
    # Example 1 - no refueling needed
    assert min_refuel_stops(1, 1, []) == 0
    
    # Example 2 - impossible
    assert min_refuel_stops(100, 1, [[10,100]]) == -1
    
    # Example 3 - optimal strategy
    assert min_refuel_stops(100, 10, [[10,60],[20,30],[30,30],[60,40]]) == 2
    
    # All reachable stations
    assert min_refuel_stops(100, 25, [[25,25],[50,50]]) == 2
    
    # Single optimal station
    assert min_refuel_stops(100, 10, [[10,100]]) == 1
    
    # No stations but reachable
    assert min_refuel_stops(10, 10, []) == 0
    
    print("All tests passed!")

test_min_refuel_stops()

Interview Tips

  1. Greedy Insight: Explain why choosing max fuel station is optimal
  2. Retroactive Decisions: Clarify that we can decide which stations to use after passing them
  3. Heap Choice: Max-heap to efficiently get best fuel option
  4. Edge Cases: Handle impossible cases and no refueling needed
  5. Alternative Approaches: Mention DP but explain why greedy is better

Follow-up Questions

  1. Minimum Cost: Stations have different prices for fuel
  2. Fuel Efficiency: Car has varying fuel efficiency
  3. Multiple Cars: Coordinate multiple vehicles
  4. Real-time Decisions: Must decide at each station immediately
  5. Fuel Capacity Limit: Car has maximum fuel tank capacity

Common Mistakes

  1. Greedy Proof: Not understanding why greedy approach works
  2. Reachability Logic: Incorrect calculation of reachable stations
  3. Heap Management: Wrong heap type or operations
  4. Edge Cases: Not handling impossible or trivial cases
  5. Position vs Distance: Confusing station positions with distances

Concept Explanations

Greedy Optimality: The key insight is that when we run out of fuel, we should have refueled at the station with maximum fuel among all stations we’ve passed. This retrospective decision-making is optimal because it maximizes our fuel for the remaining journey.

Max-Heap for Choices: As we travel, we collect all reachable stations in a max-heap. When we need to refuel, we select the station that gives us the most fuel, maximizing our future options.

When to Apply: This pattern works for optimization problems where you can make retroactive decisions and the greedy choice (maximum benefit) leads to optimal solutions. It’s particularly useful for resource management problems with deferred decision-making.