Jump Game (LeetCode 55)

The problem

You start at index 0 of an array nums of non-negative integers. nums[i] is the maximum jump length from index i; you may jump any distance from 0 up to that. Return True if you can reach the last index, otherwise False.

Input:  nums = [2, 3, 1, 1, 4]
Output: True

Input:  nums = [3, 2, 1, 0, 4]
Output: False

In the first, jump 0 → 1 → 4. In the second, every path lands on index 3, whose value is 0, so index 4 is out of reach.

How to think about it

Start with brute force. From each index, try every jump length and recurse. That explores an exponential number of paths. A DP version marks good[i] = “can reach the end from i” by checking every jump from i, which is O(n²) in the worst case.

The key insight: reachable indices form one solid block. If you can reach index j, you can also reach every index before it, because jumps can be any length up to the maximum. So the whole set of reachable indices is just 0..reach. You never need a table of booleans, only one number: the furthest index reachable so far.

Scan and extend. Walk left to right. At index i, if i > reach, then i and everything after it is unreachable, so return False. Otherwise i is reachable, and from it you can get to i + nums[i], so reach = max(reach, i + nums[i]). If the scan finishes, the last index was reachable.

Which pattern is this? A 1-D reachability DP that collapses into a greedy scan. The tell is “can you reach the end” with variable jump lengths: the DP state shrinks to a single running maximum. The same idea appears in the greedy lesson.

Approach

1. Set reach = 0.
2. For each index i with value x:
   • If i > reach, return False (you can’t stand here).
   • Otherwise set reach = max(reach, i + x).
3. If the loop ends, return True.

Solution

def can_jump(nums):
    reach = 0                                     # furthest index reachable so far
    for i, x in enumerate(nums):
        if i > reach: return False                # this index is beyond reach: stuck
        reach = max(reach, i + x)                 # extend the reachable block
    return True
# can_jump([2,3,1,1,4]) -> True ;  can_jump([3,2,1,0,4]) -> False

Dry run

On [3, 2, 1, 0, 4] (the failing case):

On [2, 3, 1, 1, 4], reach goes 2, 4, 4, 4, 8 and the loop finishes, so it returns True.

Complexity

• Time: O(n). One pass, constant work per index.
• Space: O(1). A single integer replaces the good[] table.

Edge cases and pitfalls

• Single element ([0]) returns True: you are already at the last index.
• Zeros are only traps if you can’t jump over them. [2, 0, 0] is True because index 0 reaches index 2 directly.
• Early exit. You can return True as soon as reach >= len(nums) - 1; it’s an optimisation, not a correctness fix.
• Greedily taking the longest jump from each spot is wrong; tracking the furthest reach over all visited spots is what makes it correct.

Related problems

• Jump Game II (LeetCode 45): you can always reach the end; find the fewest jumps with the same furthest-reach idea.
• Gas Station (LeetCode 134): another one-pass greedy that replaces an O(n²) simulation.
• Climbing Stairs (LeetCode 70): the counting cousin, where each step reaches a fixed distance ahead.