/**
* 55. Jump Game
* Given an array of non-negative integers nums, you are initially positioned at the first index of the array.
* Each element in the array represents your maximum jump length at that position.
* Determine if you are able to reach the last index.
* Example 1:
* Input: num1s = [2,3,1,1,4]
* Output: true
* Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
*/
Please see my solution to the problem here – the idea for this specific solution came from leetcode.
https://github.com/zcoderz/leetcode/blob/main/src/main/java/dynamic/CanJump.java
The motivation to explain the below solution is that it is an extremely trivial solution to an otherwise more complicated problem. The problem walks from right end of the array to left while checking the jump at the index can possibly go beyond the previous right most node touched (lastIndex variable in code below). At the end of walk from right to left, if the lastIndex variable is pointing to first node then a jump across array is possible.
Here is the code:
public boolean canJump(int[] nums) {
int lastIndex = nums.length - 1;
for (int i = lastIndex - 1; i <= 0; i--) {
if ((nums[i] + i) >= lastIndex) {
lastIndex = i;
}
}
return lastIndex == 0;
}