45. Jump Game II

https://leetcode.com/problems/jump-game-ii/

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

Example:

Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
    Jump 1 step from index 0 to 1, then 3 steps to the last index.

Note:

You can assume that you can always reach the last index.

---

Intuition
Number of jumps required on last step = 0
If any other array element is 0, there are no jumps possible out of that position, number of steps to reach last element = infinity .. Integer.MAX_VALUE

At every previous element,
min number of steps = 1 + min (steps to reach to last from each next position)
if the min(from each next position) == Integer.MAX_VALUE
then we cannot move from that step to last step
For eg., 5, 1, 0, 4
We cannot move from 1 to 4 - so number of steps at 1 = Integer.MAX_VALUE
Continue this till the first element

We can use the original array itself to store the minimums from each position
---
Time -
Space - O(n)
---
Related problems
55-jump-game
1306-jump-game-iii
1345-jump-game-iv

---