Problem
Given an array where each element is the maximum jump length from that position, determine if you can reach the last index.
Example
Input: [2,3,1,1,4]
Output: trueSolution
Greedy: track the farthest reachable index as you iterate. If you ever fall behind, return false.
def can_jump(nums):
farthest = 0
for i in range(len(nums)):
if i > farthest: return False
farthest = max(farthest, i + nums[i])
return Truefunction canJump(nums) {
let farthest = 0;
for (let i = 0; i < nums.length; i++) {
if (i > farthest) return false;
farthest = Math.max(farthest, i + nums[i]);
}
return true;
}bool canJump(vector<int>& nums) {
int farthest = 0;
for (int i = 0; i < nums.size(); i++) {
if (i > farthest) return false;
farthest = max(farthest, i + nums[i]);
}
return true;
}public boolean canJump(int[] nums) {
int farthest = 0;
for (int i = 0; i < nums.length; i++) {
if (i > farthest) return false;
farthest = Math.max(farthest, i + nums[i]);
}
return true;
}Complexity
- Time: O(n)
- Space: O(1)
Explanation
Greedy works because if we can reach index i, we have all options from 0 to i available. Track the maximum reach.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?