DSAMotivator

Jump Game

Medium·🍀 Greedy·Open on LeetCode ↗

Each entry says the furthest you may jump forward from that position. Starting at the first, decide whether the last is reachable.

nums = [3, 1, 0, 4, 1, 1, 2]step 1/16
3
1
0
4
1
1
2
0
1
2
3
4
5
6
furthest
reach
0

Carry one number: the furthest index anything can reach so far.

1def can_jump(nums):
2    reach = 0
3    for i, n in enumerate(nums):
4        if i > reach:
5            return False
6        reach = max(reach, i + n)
7    return True
Read the 16 steps as text
  1. 1Carry one number: the furthest index anything can reach so far.
  2. 2At index 0, which allows a jump of 3.
  3. 3From here you can get to index 3. Reach extends to 3.
  4. 4At index 1, which allows a jump of 1.
  5. 52 is no further than 3. Reach is unchanged.
  6. 6At index 2, which allows a jump of 0.
  7. 72 is no further than 3. Reach is unchanged.
  8. 8At index 3, which allows a jump of 4.
  9. 9From here you can get to index 7. Reach extends to 7.
  10. 10At index 4, which allows a jump of 1.
  11. 115 is no further than 7. Reach is unchanged.
  12. 12At index 5, which allows a jump of 1.
  13. 136 is no further than 7. Reach is unchanged.
  14. 14At index 6, which allows a jump of 2.
  15. 15From here you can get to index 8. Reach extends to 8.
  16. 16Reach never fell behind, so the last index is reachable.

The idea

The instinct is to search — try every jump length from every position and see if any route arrives. That's exponential, and memoizing it is still O(n²).

But you never actually need to know *which* route works. You only need to know how far it is possible to get, and that is a single number.

Sweep left to right carrying the furthest index reached so far. At position i you can extend that to i + nums[i]. If the sweep ever arrives at a position further than anything could reach, there's a gap nothing crosses and the answer is no.

The reason greedy is safe here — and it's the question an interviewer will ask — is that reachability is downward closed: if you can reach index k, you can reach every index before it, because the jumps allow any distance up to the maximum. So one running maximum captures everything a full search would find.

The approach

  1. 1Keep `reach`, the furthest index known to be reachable, starting at 0.
  2. 2Walk forward. If the current index is beyond `reach`, no route got here — return false.
  3. 3Otherwise extend `reach` to the larger of itself and i + nums[i].
  4. 4Surviving the whole sweep means the last index was reachable.

Complexity

Time
O(n)
Space
O(1)

One pass and one integer. No route is ever reconstructed because none is asked for.

Code

def can_jump(nums):
    reach = 0
    for i, n in enumerate(nums):
        if i > reach:
            return False
        reach = max(reach, i + n)
    return True

What goes wrong

  • •Checking `reach >= last` only at the end. It's correct but does needless work; bailing the moment i passes reach is what makes early exit possible.
  • •Treating a zero as fatal. A zero is only fatal if nothing behind it jumps over it — plenty of arrays contain zeros and still succeed.
  • •Confusing this with Jump Game II, which asks for the minimum number of jumps. Same array, different algorithm — that one needs the current jump's boundary tracked as well.