510. Jump Game II
0
Hard
Given an array of non-negative integers arr, a monkey starts at the first index of the array. Each element in the array arr[i] represents the maximum length of a forward jump from index i. The monkey wants to reach the last index in the minimum number of jumps. Help the monkey find the minimum number of jumps required to reach the last index. It is guaranteed that the monkey can always reach the last index.
Input Format
The first line of input should contain an integer N, the size of the array. The second line should contain N integers, representing the elements of the array.
Output Format
Print the minimum number of jumps the monkey needs to reach the last index.
Example
Input
5
2 3 1 1 4
Output
2
Constraints
1<=N<=10^4
0<=arr[i]<=1000
0<=arr[i]<=1000
Loading...
View Submissions
Console