Jump Game

Jump Game looks like it needs path-finding, but a single greedy scan settles it. It teaches a habit worth keeping: track one running number — the farthest you can reach — instead of simulating every possible jump.

The slow way first

The brute-force idea is to try every jump: from index i you could land on i+1, i+2, … up to i + nums[i], and from each of those try again. Explored naively this branches into an exponential number of paths; even memoized as dynamic programming it is O(n²) (every index may scan all the indices it can jump to).

The question to ask: do I actually need to know which jumps I take? No. I only need to know whether the end is reachable at all.

The idea: track the farthest reach

Keep one number, reach: the farthest index reachable so far. Walk left to right. At each index i:

• If i > reach, there is a gap I can never cross — return false.
• Otherwise i is reachable, so I can extend my horizon: reach = max(reach, i + nums[i]).

If the scan finishes without getting stuck, the last index was always within reach — return true.

The key insight: you do not need the exact jumps. A position is reachable if and only if it sits within the farthest reach accumulated from everything to its left.

Walk through it

Step through the animation on [2, 3, 1, 1, 4]. The i pointer scans left to right; the reach marker underneath slides to the farthest index reachable so far. At i = 1, reach jumps to 4 (the last index) and never shrinks, so every later index is comfortably covered and we return true. The final step shows the trap case [3, 2, 1, 0, 4], where reach stalls at 3 and i = 4 falls past it.

Pseudocode

reach = 0                          # farthest index reachable so far
for i from 0 to len(nums) - 1:
    if i > reach:                  # a gap we cannot cross
        return false
    reach = max(reach, i + nums[i])  # extend the horizon
return true                         # made it through every index

The Python solution

def can_jump(nums):
    reach = 0
    for i in range(len(nums)):
        if i > reach:
            return False
        reach = max(reach, i + nums[i])
    return True

• reach is the only state we keep: the farthest index reachable using everything seen so far.
• if i > reach is the stuck check — the current index lies beyond the horizon, so the end is impossible.
• reach = max(reach, i + nums[i]) extends the horizon; i + nums[i] is the farthest you can land from i.
• We never decrease reach, and once it meets or passes the last index the rest of the scan trivially passes.

Complexity

The greedy version uses O(1) extra space — just the single reach variable — and one pass. That is the payoff of asking what is the minimal fact I must track? instead of simulating every choice.

When this pattern shows up

Practice