Jump Game

01 · Question

You are given an integer array nums where nums[i] is your maximum jump length from index i. Return true if you can reach the last index.

02 · Analysis

For a nonempty array of nonnegative jump lengths, reach is the farthest index reachable from positions already scanned. If i exceeds reach, all earlier options fail to reach i, so return false. Otherwise extend reach using i+nums[i]. O(n) time and O(1) space. A one-element array is already at the destination.

03 · Solution

Reference solution

1def canJump(nums: List[int]) -> bool:
2    farthest = 0
3    for i, x in enumerate(nums):
4        if i > farthest:
5            return False
6        farthest = max(farthest, i + x)
7    return True

Jump Game II