You stand on the first index of an array nums. Each value nums[i] is the longest jump you may make from index i (you can also jump shorter). Return true if you can reach the last index, otherwise false.
- 1 <= nums.length <= 10^4
- 0 <= nums[i] <= 10^5
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
A DP or DFS that marks every reachable index from every other index costs O(n^2). The key fact: the set of reachable indices is always a prefix [0, far], because if you can reach index j you can reach every index before it with a shorter jump. So keep one number far. At each index i <= far, update far = max(far, i + nums[i]). The greedy is safe because extending far as much as possible never removes an option. If some i is greater than far, nothing can reach it and the answer is false.
Algorithm
- Set
far = 0. - For each index
i: ifi > far, return false. - Update
far = max(far, i + nums[i]). - If
far >= n - 1, return true early. After the loop, return true.
O(n)Space: O(1)nums = [0]. A common follow-up is Jump Game II: the minimum number of jumps.class Solution: def canJump(self, nums: List[int]) -> bool: far = 0 # farthest index reachable so far for i, x in enumerate(nums): if i > far: return False # index i cannot be reached far = max(far, i + x) if far >= len(nums) - 1: return True return True