Jump Game
Medium· Greedy Reach
Problem
You start at index 0 of an array where nums[i] is the maximum jump length from position i. Return true if you can reach the last index.
Examples
Input: nums = [2,3,1,1,4]
Output: true
Jump 1 step to index 1, then 3 steps to the end.
Input: nums = [3,2,1,0,4]
Output: false
Every route lands on index 3, whose value is 0.
Constraints
- • 1 <= nums.length <= 10^4
- • 0 <= nums[i] <= 10^5
Hints & approach
Hint 1
You do not need to know which jumps to take, only how far you could possibly get.
Hint 2
Track the furthest index reachable so far as you scan left to right.
Approachtry the hints first
Maintain reach, the furthest index reachable using positions seen so far. Scan each index i; if i > reach, it is unreachable and so is everything after, so return false. Otherwise update reach = max(reach, i + nums[i]). If the scan completes, the last index is reachable.
Time O(n) · Space O(1)