Module 22 · Greedy Algorithms and Kadane-Style State

215. Jump Game Reachability

Bridge · Download this solution · All solutions and shared helpers

Problem

Given nonnegative jump limits nums, return whether the last index is reachable from index zero. From i, any forward jump of length at most nums[i] is allowed. A singleton succeeds without jumping; empty input returns false because it has no start or destination.

Examples

Example 1

can_jump([2,3,1,1,4])
=> True

Reach extends from the early prefix to the final index.

Example 2

can_jump([3,2,1,0,4])
=> False

The zero at the boundary prevents crossing to index 4.

Example 3

can_jump([0])
=> True

The starting position is already the destination.

Reveal the worked solution and reasoning

Why this mechanism works

If every position through farthest is reachable, a reachable index i can extend this prefix through i+nums[i]. Only that boundary matters; enumerating individual jump choices adds no information. Encountering an index beyond the boundary proves that no earlier reachable position can bridge the gap.

State and boundaries

farthest is the greatest index reachable using processed positions. All indices from zero through it are reachable.

Protocol

Reject empty input.
Scan indices from zero.
Reject when i>farthest.
Extend farthest with i+nums[i].
Succeed once the final index is covered.

Visualization

[3,2,1,0,4]
reachable frontier stays at index 3
index 4 lies beyond it -> failure

Python implementation

def can_jump(nums):
    if not nums:
        return False
    farthest = 0
    for i, jump in enumerate(nums):
        if i > farthest:
            return False
        farthest = max(farthest, i + jump)
        if farthest >= len(nums) - 1:
            return True
    return False

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

can_jump([2,3,1,1,4])

L2 can_jump: if not nums:
nums=[2, 3, 1, 1, 4]

L4 can_jump: farthest = 0
nums=[2, 3, 1, 1, 4]; farthest=0

L5 can_jump: for i, jump in enumerate(nums):
nums=[2, 3, 1, 1, 4]; farthest=0; i=0; jump=2

L8 can_jump: farthest = max(farthest, i + jump)
nums=[2, 3, 1, 1, 4]; farthest=2; i=0; jump=2

L5 can_jump: for i, jump in enumerate(nums):
nums=[2, 3, 1, 1, 4]; farthest=2; i=1; jump=3

L8 can_jump: farthest = max(farthest, i + jump)
nums=[2, 3, 1, 1, 4]; farthest=4; i=1; jump=3

Result: True. Reach extends from the early prefix to the final index.

can_jump([3,2,1,0,4])

L2 can_jump: if not nums:
nums=[3, 2, 1, 0, 4]

L4 can_jump: farthest = 0
nums=[3, 2, 1, 0, 4]; farthest=0

L5 can_jump: for i, jump in enumerate(nums):
nums=[3, 2, 1, 0, 4]; farthest=0; i=0; jump=3

L8 can_jump: farthest = max(farthest, i + jump)
nums=[3, 2, 1, 0, 4]; farthest=3; i=0; jump=3

L5 can_jump: for i, jump in enumerate(nums):
nums=[3, 2, 1, 0, 4]; farthest=3; i=1; jump=2

L5 can_jump: for i, jump in enumerate(nums):
nums=[3, 2, 1, 0, 4]; farthest=3; i=2; jump=1

L5 can_jump: for i, jump in enumerate(nums):
nums=[3, 2, 1, 0, 4]; farthest=3; i=3; jump=0

L5 can_jump: for i, jump in enumerate(nums):
nums=[3, 2, 1, 0, 4]; farthest=3; i=4; jump=4

Result: False. The zero at the boundary prevents crossing to index 4.

Why the solution is correct

The reachable-prefix property holds at zero. From a reachable position all intermediate forward destinations up to its jump limit are allowed, so taking the maximum preserves a contiguous reachable prefix. If the scan reaches a gap, no processed position can cross it and no unprocessed position is reachable to help.

Time and space

O(n) time and O(1) auxiliary state.

Common mistakes

Updating reach from an unreachable position invents a path. Treating nums[i] as an exact jump length violates the at-most contract.

Reasoning card

State: farthest is the greatest index reachable using processed positions. All indices from zero through it are reachable.

Invariant: Every index <= farthest is potentially reachable.

Decision to rehearse: Maintain the farthest reachable frontier.

Finish: Succeed once the final index is covered

Transfer exercise

Allow backward jumps too. Explain why one forward frontier no longer summarizes all reachable states.