Can Jump - Given an array of non-negative integers, you're initially at the first index. Each element represents your maximum jump length at that position. Determine if you can reach the last index.
MediumYou start at index 0 of an integer array nums. Each element is the maximum number of steps you can jump forward from that position. Return true if you can reach the last index, and false otherwise.
Example 1
Input: nums = [2, 3, 1, 1, 4] Output: true
Jump 1 step to index 1, then 3 steps to the last index.
Example 2
Input: nums = [3, 2, 1, 0, 4] Output: false
Every path lands on index 3, whose jump length is 0, so you can never get past it.
Constraints
1 <= nums.length <= 10^40 <= nums[i] <= 10^5
Approach
Marking each index as reachable or not, and spreading reachability forward from each one, takes O(n²) time in the worst case. You can do better by noticing that the reachable indices always form an unbroken prefix: if you can reach index j, you can also reach every index before it. So a single number describes everything you can reach: the farthest reachable index. Walk the array, and at each index you can reach, extend farthest with i + nums[i]. If farthest covers the last index, return true. If you arrive at an index past farthest, return false.
Steps
- Set
farthest = 0. - For each index
i, returnfalseifi > farthest. - Otherwise, set
farthest = max(farthest, i + nums[i]). Iffarthestis at least the last index, returntrue.
Complexity
- Time:
O(n). One pass over the array. - Space:
O(1).
Common mistakes
- Always taking the longest jump from each index. A shorter jump can land on an index that reaches farther.
- Returning
falseas soon as you see a0. A zero only blocks you if no earlier index can jump past it.
Related questions
Each element of an array of non-negative integers may be lowered to any smaller non-negative value. What is the largest MEX the array can reach?Given an array of integers, find the next greater integer for each element in the array.Given an array of n integers and a number k, find the maximum number of elements whose sum is less than k, and return their sum.Related courses


