108. Jump Game II

Given an integer array nums where nums[i] is the maximum jump length from index i, return the minimum number of jumps to reach the last index. You can always reach the last index.

Input: Integer array nums of length n.

Output: Integer — minimum number of jumps to reach last index.

Examples

Input: [2,3,1,1,4]
Output: 2
Explanation: Jump 1 step to index 1, then 3 steps to last. 2 jumps total.

Input: [2,3,0,1,4]
Output: 2
Explanation: Jump to index 1, then to index 4. 2 jumps.

Input: [1,2,3,4,5]
Output: 3
Explanation: 1→2→4→5 (indices 0→1→3→4). 3 jumps.

Constraints

• 1<=nums.length<=10^4
• 0<=nums[i]<=1000
• Always reachable.

Asked by