Reach the Last Index with Minimum Jumps
You are given a list of non-negative integers nums and begin at its first index. Each value represents the maximum number of positions you may jump forward from that index.
Determine whether the last index is reachable. For an input where the last index is guaranteed to be reachable, also determine the minimum number of jumps required to reach it.
Jump Rules
- You start at index
0.
- From index
i, you may jump to any index from i + 1 through i + nums.get(i), provided that the destination is inside the list.
- You may only jump forward.
- The last index is
nums.size() - 1.
- If the list contains one element, you are already at the last index.
Method Signatures
Check Whether the Last Index Is Reachable
boolean canJump(List<Integer> nums)
- Return
true if it is possible to reach the last index.
- Return
false if no sequence of valid jumps can reach the last index.
Find the Minimum Number of Jumps
int jump(List<Integer> nums)
- The last index is guaranteed to be reachable for this method.
- Return the minimum number of valid jumps needed to reach the last index.
- Return
0 when nums contains one element.
Constraints
Constraints for canJump
1 ≤ nums.size() ≤ 10,0000 ≤ nums.get(i) ≤ 100,000
Constraints for jump
1 ≤ nums.size() ≤ 10,0000 ≤ nums.get(i) ≤ 1,000- The last index is always reachable.
Examples
Example 1
canJump(nums = [1, 2, 0, 0])
Output: true
Jump from index 0 to index 1, and then jump to the last index.
Example 2
canJump(nums = [2, 0, 0, 1])
Output: false
The farthest reachable index is 2, so index 3 cannot be reached.
Example 3
jump(nums = [1, 3, 2, 1, 1])
Output: 2
One optimal sequence jumps from index 0 to index 1, and then from index 1 to index 4.
Example 4
jump(nums = [0])
Output: 0
The first index is also the last index, so no jump is needed.