LeetCode 55 · Greedy

Jump Game, explained with a picture

A frog checking how far it could ever reach.

MediumGreedy
▶ Watch it step by step

The problem

Each number says the longest jump you may make from that position. Starting at the first position, can you reach the last one?

Input:  [2, 3, 1, 1, 4]
Output: true

Picture it

Picture a frog on a row of lily pads. Each pad shows its jump range. Walking along the pads, we keep track of the farthest pad reachable so far. If we ever stand on a pad beyond that point, we could never have got here, so the frog is stuck. If the farthest reach covers the last pad, the answer is yes.

How to recognise it

  • Each position gives a maximum jump, and any shorter jump is also allowed, so reachability has no gaps: if you can get to position p, you can get to every position before p that you passed.
  • The question is yes or no ("can I reach the end?"), not "how", so you only need to track a single frontier.
  • Up to 10^4 positions with jumps up to 10^5, so exploring every path is hopeless.
  • When "the set of reachable positions" is always a prefix, keep one number: the farthest position reachable so far.

Start with brute force

Try every jump length from each position, depth first, and report whether any path reaches the last position.

def can_jump_brute(pads):
    last = len(pads) - 1
    def go(i):
        if i >= last:
            return True
        for step in range(1, pads[i] + 1):
            if go(i + step):
                return True
        return False
    return go(0)

Without remembering failures, the same positions are explored again and again. For a row like [k-1, k-2, …, 1, 0, x] where the end is unreachable, the number of calls doubles with every extra pad: 25 pads already means about 8 million calls, and the limit is 10,000. Space is O(n) for the recursion.

From brute force to the idea

  1. Find the waste. The brute force explores each pad from every path that reaches it, but a pad is either reachable or not.
  2. Reachable positions form a prefix. If you can reach position p, you can land on any earlier position by choosing a shorter jump. So everything from 0 to the farthest reachable position is reachable.
  3. Track one number. Let reach be the farthest index reachable so far. Scan left to right; at pad i, the jump from i can extend it: reach = max(reach, i + jump).
  4. Detect failure. If the scan arrives at a pad i with i > reach, nothing could reach it, and nothing beyond, so return False.
  5. Success. If the loop finishes, every pad including the last was within reach, so return True.

This is the key idea: reachability is a prefix, so keep the farthest reach and check each pad against it.

The key idea

Greedy: reach = max(reach, i + nums[i]); fail if i > reach. O(n).

Python solution

def can_jump(pads):
    reach = 0
    for i, jump in enumerate(pads):
        if i > reach:
            return False               # this pad can never be reached
        reach = max(reach, i + jump)
    return True

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceExponential: every pad branches over all its jump lengthsO(n): recursion depth
Greedy reach (shown code)O(n): one pass, one comparison and one max per padO(1): a single variable

Edge cases

  • One pad ([0]): returns True; you are already at the end.
  • Stuck on a zero ([3, 2, 1, 0, 4]): returns False; the farthest reach is 3, and the zero is a wall.
  • Zero that can be jumped over ([2, 3, 1, 1, 4]): returns True.
  • Start is zero but there is more ([0, 1]): returns False.
  • Zero in the middle but reachable ([2, 0, 0]): returns True; the first pad jumps straight to the end.
  • Empty list: returns True because the loop never runs; the problem guarantees at least one pad.
  • Huge jump ([100000, 0, 0]): returns True; reach goes past the end, which is fine.

Common mistakes

  • Overwriting instead of taking a maximum (reach = i + jump), so a later short jump shrinks the reach: [3, 0, 0, 0] wrongly returns False.
  • Checking i >= reach instead of i > reach, which rejects even the starting pad.
  • Returning False as soon as a pad holds 0. A zero is a wall only when reach cannot get past it, as [2, 0, 0] shows.
  • Building a full table of reachable positions. It works in O(n²) but wastes the prefix property.
Your turn: how many pads can you reach?

Return the number of positions you can reach from the first pad (counting the first). For [3, 2, 1, 0, 4] the answer is 4 (positions 0 to 3), and for [2, 3, 1, 1, 4] it is 5. Describe your approach, then write it if you like.

Compare with our answer

The same scan works. When the scan arrives at a pad it cannot reach, the pads before it are exactly the reachable ones.

def count_reachable(pads):
    reach = 0
    for i, jump in enumerate(pads):
        if i > reach:
            return i
        reach = max(reach, i + jump)
    return len(pads)

count_reachable([3, 2, 1, 0, 4]) is 4 and count_reachable([0, 1]) is 1. Time O(n), space O(1).

A strong answer mentions: that reachable positions form a prefix, returning the index of the first unreachable pad, returning the full length if the scan finishes, and the same single-variable reach.

Check what stuck

1. Stepping stones are laid in a row, and from stone i you may jump any distance up to limit[i]. With 10,000 stones, how do you decide if the last stone can be reached from the first?

2. Why is the shown code O(n) time even though each pad allows many jump lengths?

3. A learner changes the update to reach = i + jump (no max). For which input does the function now return the wrong answer?

Score 60% or more and the lesson is marked complete.