You stand on the first element of an integer array nums, where nums[i] is the farthest you may jump forward from position i (any shorter jump is allowed too). Return true if the last position is reachable, false otherwise.
Examples
Example 1:
Input: nums = [2,3,1,1,4]
Output: true
Explanation: 0 -> 1 -> 4, or 0 -> 2 -> 3 -> 4.
Example 2:
Input: nums = [3,2,1,0,4]
Output: false
Explanation: every route lands on the 0 at position 3 and dies there.
Example 3:
Input: nums = [0]
Output: true
Explanation: you are already standing on the last position.
Example 4:
Input: nums = [2,0,0]
Output: true
Constraints
1 <= nums.length <= 10^4
0 <= nums[i] <= 1000
Prerequisites
Greedy arguments — and the habit of asking what would have to be true for the local choice to be safe, before trusting it.
How to think about it
1. Farthest Reach So Far Optimal
Intuition
Forget which jumps to take and track only how far the array can reach. Standing at a position beyond that reach means no route exists; otherwise extend the reach by what this position offers. The greedy is safe because reach only grows, so a position that is reachable at all is reachable by the time the scan arrives.
Algorithm
1. Keep the farthest index reachable, starting at 0. 2. Walk the array; a position past the reach means false. 3. Otherwise extend the reach to index plus its jump length. 4. Surviving the walk means the end is reachable.
Time & Space
Time O(n). Space O(1). The DP version is O(n^2) and the one this argument replaces.