Reach the Last Index | Practice

You start at index 0 of a list of non-negative integers nums. From index i you may jump forward by any number of steps from 1 up to nums[i]; from an index holding 0 you can't move.

Return true if you can reach the last index, and false otherwise.

Example 1

Input: nums = [2, 3, 0, 1, 4]
Output: true

Jump 1 step to index 1, then 3 steps to the last index.

Example 2

Input: nums = [3, 1, 1, 0, 5]
Output: false

No jump gets past index 3, which holds 0.

Constraints

nums holds 1 to 10⁴ numbers.
0 ≤ nums[i] ≤ 10⁵

Show the pattern

Greedy

You never need to know how you reach a position, only how far you could get from everything reachable so far: keep the furthest reachable index and push it forward in one greedy scan.

See greedy in a visualiser

Show the approach

Keep reach, the furthest index you can get to using the indices seen so far. Every index up to reach is reachable, because a jump may be shorter than its maximum.

Walk from left to right. If the current index i is beyond reach, nothing before it can get you here, so return false. Otherwise stretch reach to i + nums[i] if that is further. If the walk gets through every index, the last one is reachable.

Time: O(n) · Space: O(1)