Show problems as
Classic problem #45MediumArrayDynamic ProgrammingGreedy

Jump Game II

Real-world version: Fewest Drone Flights
Tracked in this browser only
Read Jump Game II on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A courier drone sits on the first of a row of rooftop landing pads, indexed from 0 to len(reach) - 1.

You are given an integer array reach. When the drone lifts off from pad i, its remaining battery lets it settle on any pad from i + 1 up to and including i + reach[i], whichever of those pads exist. A single takeoff-and-landing counts as one flight. A pad whose value is 0 has no charging coil, so a drone that lands there can never lift off again.

Return the fewest flights that carry the drone from pad 0 to the last pad. The route planner only ever hands you a row in which the last pad is attainable, and a drone that already starts on the last pad needs no flights at all.

Examples

Example 1

Input
reach = [3, 1, 1, 4, 2]
Output
2

One flight of three pads lands on pad 3, then a flight of a single pad finishes the trip. No single flight spans four pads from the start.

Example 2

Input
reach = [1, 4, 0, 0, 2, 1]
Output
2

Hop to pad 1, whose charge of 4 covers the two dead pads and lands directly on pad 5.

Example 3

Input
reach = [0]
Output
0

The only pad in the row is also the destination.

Constraints

  • 1 <= reach.length <= 10^4
  • 0 <= reach[i] <= 1000
  • The last pad is always attainable from pad 0

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def fewest_flights(reach: list[int]) -> int:
Java
public int fewestFlights(int[] reach)

More on the same topics