Problem
You are given an integer arraynums, where nums[i] represents the maximum number of positions you can jump forward from index i.
You start at index
0 and can jump to any position between i + 1 and i + nums[i]. Return true if you can reach the last index. Otherwise, return false.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
nums = [2,3,1,1,4]Output
trueSolution
This problem can be solved using a Greedy Approach.As we move through the array, we keep track of the farthest index that can currently be reached using
maxReach.
If the current index is greater than
maxReach, it means we cannot reach this position, so we cannot reach the last index either.
Otherwise, we update
maxReach using the maximum position that can be reached from the current index.
If
maxReach reaches or passes the last index, we can immediately return true.
class Solution {
public boolean canJump(int[] nums) {
int reachableIndexSoFar = 0;
int n = nums.length;
for (int i = 0; i < n; i++) {
// Current index is unreachable
if (i > reachableIndexSoFar)
return false;
int reachableIndexFromCurrentIndex = i + nums[i];
// Last index is reachable
if (reachableIndexFromCurrentIndex >= n - 1)
return true;
reachableIndexSoFar = Math.max(reachableIndexSoFar, reachableIndexFromCurrentIndex);
}
return false;
}
}
Complexity
Each position is processed once, resulting inO(n) time complexity, and only a constant number of variables is used, resulting in O(1) space complexity.