Jump Game - Greedy Explained Visually

Why it works

The only thing that matters is the frontier: any index within it is reachable by some path, so maintaining the maximum is sufficient - no need to track how. One pass, O(n) time, O(1) space, and no recursion.

The problem

Given an integer array nums where nums[i] is the maximum jump length from position i, return true if you can reach the last index from index 0.

Hints

• Iterate forward, tracking the farthest index reachable so far.
• If your current index exceeds the farthest reachable, you are stuck.
• max_reach = max(max_reach, i + nums[i])
• If i <= max_reach at every step and max_reach >= last_index, return True.

Test cases

Reference starter code

def can_jump(nums):
    # Track the farthest index reachable
    pass

print(can_jump([2, 3, 1, 1, 4]))  # True
print(can_jump([3, 2, 1, 0, 4]))  # False
print(can_jump([0]))              # True

Try it yourself

Solve it in the browser editor with real test cases and instant feedback - free, no signup needed.