Greedy The best choice now
492. Jump Game II
You are given an array of integers nums. You start at index 0, and nums[i] is the longest jump you can
make from index i. A jump from i can land on any index from i + 1 to i + nums[i], so a jump may be
shorter than nums[i].
Return the fewest jumps you need to reach the last index. The input always lets you reach it.
Example 1
Input: nums = [2, 4, 1, 1, 0, 2, 1]
3Explanation: One best path is 0 → 1 → 5 → 6. Jumping the full 2 steps first lands on index 2, and from there every path gets stuck on the 0 at index 4.
Example 2
Input: nums = [6, 2, 9, 1, 0, 3, 1]
1Explanation: A jump of 6 steps from index 0 lands on the last index. The 9 at index 2 is not needed.
Example 3
Input: nums = [0]
0Explanation: The array has one element, so we start on the last index and need no jump.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ nums.length ≤ 1050 ≤ nums[i] ≤ 109- The last index can always be reached from index 0.
Clarifying questions
What you would ask an interviewer before writing any code.