The problem
You start at index 0. From index i you may jump forward any distance up to nums[i]. Return true if you can reach the last index.
Examples
01
- Input
nums = [2, 3, 1, 1, 4]
- Output
true
02
- Input
nums = [3, 2, 1, 0, 4]
- Output
false
Constraints
- 1 ≤ nums.length ≤ 10⁴
- 0 ≤ nums[i] ≤ 10⁵
The idea
The reachable indices always form one unbroken stretch from 0: if you can get to i, you can get to everything before it. So track only its end, reach.
Walk forward. Each index inside the stretch can push it to i + nums[i]. If you ever stand on an index beyond reach, there is a gap no jump crosses — the answer is false.
- Time
- O(n)
- Space
- O(1)
Solution · every language run against every case
class Solution: def canJump(self, nums: List[int]) -> bool: reach = 0 # the furthest index reachable so far for i, x in enumerate(nums): if i > reach: return False # a gap nothing can jump across reach = max(reach, i + x) return True