#182MediumGreedy· Interval Reach (Jump Game)

Fewest Hops to the Last Platform

A delivery drone moves along a row of charging platforms numbered `0` to `n - 1`, starting on platform 0. The number `hops[i]` is the largest distance the drone can fly forward in one hop when it takes off from platform `i`; it may also choose any shorter forward hop (at least 1). Return the minimum number of hops needed to reach the last platform. You may assume the last platform is always reachable.

Input format

`hops`: an array of non-negative integers, one per platform.

Output format

An integer: the minimum number of hops from platform 0 to platform n - 1.

Examples

Input: hops = [2, 3, 1, 1, 4]

Output: 2

Hop from platform 0 to platform 1 (distance 1), then from platform 1 to platform 4 (distance 3): 2 hops.

Input: hops = [2, 3, 0, 1, 4]

Output: 2

Platform 2 is a dead end, but it can be flown over: 0 -> 1 -> 4 still takes 2 hops.

Input: hops = [0]

Output: 0

The drone is already on the last platform, so no hops are needed.

Constraints

1 <= hops.length <= 10^5
0 <= hops[i] <= 1000
The last platform is reachable from platform 0.

Study first

Greedy Algorithms

#greedy
#arrays
#jump-game
#breadth-first-search