Jump Game

You don't need to remember every route. You only need to know how far all routes together can reach.

Backward reachability table

Dynamic programming (DP) stores answers to smaller versions of a problem so you can reuse them. Let reachable[i] say whether the last index can be reached from i. The last index is already safe. Moving right to left, inspect every landing position allowed by nums[i]; if any landing is safe, i is safe too.

def can_jump(nums: list[int]) -> bool:
    n = len(nums)
    reachable = [False] * n
    reachable[-1] = True
 
    for i in range(n - 2, -1, -1):
        limit = min(n - 1, i + nums[i])
        for landing in range(i + 1, limit + 1):
            if reachable[landing]:
                reachable[i] = True
                break
    return reachable[0]

Time O(n²) in the worst case — many indices may inspect nearly the whole suffix. Space O(n) for the reachability table.

Furthest reachable index

Scan only the positions already inside a reachable prefix. Each one offers a new right endpoint, i + nums[i]; retain the largest endpoint offered so far.

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

The exchange argument is a proof that swapping another choice for the greedy choice can't hurt the final answer. After scanning through index i, imagine any collection of jump sequences that reaches the scanned prefix. Exchange its remembered endpoint for the furthest endpoint any of those sequences offers. Every nearer landing remains available because jumps may stop short, while no competing choice unlocks an index beyond furthest. Keeping only that frontier is therefore globally optimal. If i lies beyond it, every possible route is stuck before i.

Time O(n) — each index is scanned at most once. Space O(1) — one frontier replaces the whole table.