Can You Reach the Last Index
You get an array nums of non-negative integers. You start at index 0.
The value nums[i] is the largest jump you can make from index i. From index i you can move to any index from i + 1 up to i + nums[i]. A value of 0 means you cannot move from that index.
Return true if you can reach the last index, and false if you cannot.
Note
If nums has only one element, you already stand on the last index, so the answer is true.
Hint
Walk from left to right and keep far, the largest index you can reach so far. If the current index is larger than far, you can never get there, so stop. Otherwise update far with i + nums[i]. This is O(n).
Examples
Example 1
- Input:
- [1,3,0,2,0,1]
- Output:
- true
Jump 1 step to index 1, then 2 steps to index 3, then 2 steps to index 5, which is the last index.
Example 2
- Input:
- [2,1,0,3,4]
- Output:
- false
From index 0 you can reach index 1 or 2. From both of them the furthest you can get is index 2, where the value is 0. Index 3 is never reached.
Example 3
- Input:
- [0]
- Output:
- true
The array has one element. You start on the last index, so you do not need to move.
Constraints
1 <= nums.length <= 500 <= nums[i] <= 10
Run checks your code against the 3 examples. Submit checks it against all 263 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.