mediumGreedy choice target 25 min
Jump game II
You stand on position 0 of a list nums of non-negative integers. From position i you may jump forward to any position from i + 1 up to i + nums[i], as in Jump game. This time the last position can always be reached.
Return the fewest jumps that take you from position 0 to the last position. If the list has one position, you are already there: return 0.
Example 1
Input
nums = [2, 1, 2, 1, 1, 1]Output3For example 0 to 2 to 4 to 5. Two jumps reach at most position 4, so a third is needed.
Example 2
Input
nums = [3, 4, 1, 1, 1, 1]Output20 to 1 to 5. The long first jump, to position 3, needs two more jumps after it.
Example 3
Input
nums = [0]Output0One position: you start at the end.
Constraints
1 ≤ len(nums) ≤ 105
0 ≤ nums[i] ≤ 105
The last position can always be reached.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.
Run examples checks the examples. Submit runs every test, including edge cases and, when the problem has one, a speed check on a large input.