FastPrep
Problem · Array

Minimum Refueling Stops

Learn this problem
● HardUber logoUberFULLTIMEONSITE INTERVIEW
See Uber hiring insights

Problem statement

A car starts at position 0 with startFuel units of fuel and must reach position target. It consumes one unit of fuel per unit of distance.

Each station is [position, fuel]. On reaching a station, the car may stop once and take all of that station's fuel, or skip it. Return the minimum number of stops needed to reach target, or -1 if the target is unreachable.

For this exercise, station positions are distinct and strictly between 0 and target. The input may be unsorted and may be normalized into increasing position order.

Function

minRefuelStops(target: int, startFuel: int, stations: int[][]) → int

Examples

Example 1

target = 100startFuel = 10stations = [[10,60],[20,30],[30,30],[60,40]]return = 2

Stop at positions 10 and 60. Their fuel is sufficient to reach the target in two stops.

Example 2

target = 100startFuel = 1stations = [[10,100]]return = -1

The car cannot reach the station at position 10, so no stop is possible.

Constraints

  • 1 <= target <= 10^9
  • 0 <= startFuel <= 10^9
  • 0 <= stations.length <= 2 * 10^5
  • Each station is [position, fuel], with distinct position strictly between 0 and target.
  • 1 <= fuel <= 10^9.

More Uber problems

drafts saved locally
public int minRefuelStops(int target, int startFuel, int[][] stations) {
    // Write your code here.
}
target100
startFuel10
stations[[10,60],[20,30],[30,30],[60,40]]
expected2
checking account