Jump Game
Given an array of non-negative integers, 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.
Constraints:
- 1 <= nums.length <= 1000
- 0 <= nums[i] <= 105
Examples:
Input: [2,3,1,1,4]
Output: true
Explanation: We can reach the last index by jumping from index 0 to index 1, then from index 1 to index 4.
Input: [3,2,1,0,4]
Output: false
Explanation: We cannot reach the last index because we are stuck at index 3.
Solutions
Greedy
We initialize a variable maxReach to keep track of the maximum index we can reach. We iterate through the array, and for each index, we check if it is within our current maxReach. If it is not, we return false. Otherwise, we update maxReach to be the maximum of our current maxReach and the current index plus the jump value at the current index.
public boolean canJump(int[] nums) {
int maxReach = 0;
for (int i = 0;
i < nums.length;
i++) {
if (i > maxReach) return false;
maxReach = Math.max(maxReach, i + nums[i]);
}
return true;
}Follow-up:
What if we can jump in both directions?
