Jump Game

Signal

"Can you reach the end" with per-position reach values doesn't need to enumerate paths — it only needs the single number "farthest index reachable so far," updated greedily as you scan left to right.

Approach

Track the farthest index reachable given everything seen up to now. Walk the array; if the current index is ever beyond that farthest reach, you're stuck and can't proceed. Otherwise, update the farthest reach with i + nums[i]. Reaching the end of the walk without ever getting stuck means the last index is reachable.

Skeleton

farthest = 0
for i, jump in enumerate(nums):
    if i > farthest:
        return False
    farthest = max(farthest, i + jump)
return True

Solution

def can_jump(nums: list[int]) -> bool:
    farthest = 0
    for i, jump in enumerate(nums):
        if i > farthest:
            return False
        farthest = max(farthest, i + jump)
    return True

Complexity

O(n) time — one pass. O(1) space.

Pitfalls

• Checking i > farthest (not >=) matters — landing exactly on the current farthest reach is still fine, you're not stuck yet.
• Trying to simulate every possible jump length from every index (branching recursion) is correct but exponential — the greedy farthest-reach reduces it to one pass because only the maximum reachable index ever matters, not which jump got you there.
• This only answers reachability — Jump Game II asks for the minimum number of jumps, which needs an extra "current boundary" variable on top of this.