Statement

Given an array nums of positive numbers, start from the first index and reach the last index with the minimum number of jumps, where a number at an index represents the maximum jump from that index.

For example, if the value at the current index is 33, then a maximum of 33 and a minimum of a 11 step jump can be taken in the direction of the last index of the array. You cannot move in the opposite direction, that is, away from the last index.

Let’s say you have an array of [2,3,1,5,7][2, 3, 1, 5, 7], starting from the 0th0^{th} index. It requires only two jumps to reach the last index. The first jump will be from the 0th0^{th} index to the 1st1^{st} index, i.e., only a one-step jump, and the next jump will be from the 1st1^{st} index to the 4th4^{th} index, i.e., a three-step jump.

Constraints:

  • 11 \leq nums.length 103\leq 10^3
  • 00 \leq nums[i] 103\leq 10^3
  • It’s guaranteed that you can reach the last index of nums.

Examples

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.