Greedy algorithms make the locally best choice and never look back. They are only correct when you can prove the local choice never hurts. Here the key quantity is how far can I possibly reach?
You are given a list nums; you start at index 0 and nums[i] is the maximum jump length from index i. Return True if you can reach the last index, otherwise False.
Examples
Input: nums = [2, 3, 1, 1, 4]
Output: True
Explanation: jump 1 step to index 1, then 3 steps to the last index
Input: nums = [3, 2, 1, 0, 4]
Output: False
Explanation: you always arrive at index 3, whose jump length is 0
Constraints
1 <= len(nums) <= 10**4,0 <= nums[i] <= 10**5- Target: O(n) time, O(1) space (a DP over every possible jump is O(n^2) and unnecessary)
Goals
- Identify a greedy invariant (the furthest index reachable so far) that makes a DP unnecessary
- Argue why a greedy choice is safe before trusting it
- Solve in a single left-to-right pass