LeetCode 45 · Greedy

Jump Game II, explained with a picture

Fewest hops, thinking one wave at a time.

MediumGreedy
▶ Watch it step by step

The problem

Same lily pads, and the last pad is always reachable. Find the fewest jumps needed to get there.

Input:  [2, 3, 1, 1, 4]
Output: 2   (pad 0 → pad 1 → last pad)

Picture it

Think in waves. Wave 0 is pad 0. Wave 1 is every pad reachable with one jump. Wave 2 is every pad reachable from wave 1, and so on. As we scan a wave we note how far its pads could jump; that becomes the end of the next wave. The number of waves needed to cover the last pad is the answer.

How to recognise it

  • It is Jump Game again, but now you want the fewest jumps, and the last pad is guaranteed reachable.
  • Reachable positions after k jumps form a range (everything up to some farthest point), so the jumps behave like the levels of a breadth-first search (BFS: explore everything one step away, then two steps away, and so on).
  • Up to 10^4 pads. A quadratic table (about 5 × 10^7 steps) would be borderline; one pass is expected.
  • When the answer is "number of levels until the target" and each level is a contiguous range, you can count levels by tracking the end of the current level and the farthest reach of the next.

Start with brute force

Try every jump length from every pad, recursively, and keep the smallest number of jumps.

def jump_brute(pads):
    n = len(pads)
    def go(i):
        if i >= n - 1: return 0
        best = float("inf")
        for s in range(1, pads[i] + 1):
            best = min(best, 1 + go(i + s))
        return best
    r = go(0)
    return None if r == float("inf") else r

Each pad branches over all its jump lengths and nothing is remembered, so time is exponential, and the calls double with every extra pad (a row like [10, 9, …, 1, 1] of 11 pads makes 1,024 calls; 40 such pads would make about 5 × 10^11). A table d[j] = min(d[i] + 1) over earlier pads i that can reach j fixes the repetition but is O(n²). Space is O(n) for the recursion.

From brute force to the idea

  1. Think in waves. After 0 jumps you are at pad 0. After 1 jump you can be on any pad from 1 to 0 + pads[0]. After 2 jumps, on any pad up to the farthest reach of those pads. Each wave is a range.
  2. Track the wave. end is the last pad of the current wave, and far is the farthest pad any pad in the current wave (so far) can reach.
  3. Scan left to right. At pad i update far = max(far, i + pads[i]).
  4. Cut at the wave end. When i == end, you have seen every pad of this wave, so one more jump is needed to leave it: hops += 1 and the next wave ends at far.
  5. Stop before the last pad. The loop runs to len(pads) - 2, because once you are standing on the last pad you are done.

This is the key idea: count the waves, where each wave ends at the farthest point the previous wave could reach.

The key idea

BFS by ranges: when i reaches the end of the current wave, jumps += 1 and the wave end becomes the farthest reach. O(n).

Python solution

def jump(pads):
    hops, end, far = 0, 0, 0
    for i in range(len(pads) - 1):
        far = max(far, i + pads[i])     # best reach from this wave
        if i == end:                    # finished the current wave
            hops += 1
            end = far
    return hops

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 jump lengthsO(n): recursion depth
Greedy waves (shown code)O(n): each pad is looked at onceO(1): three variables

Edge cases

  • One pad ([0]): returns 0, since the loop range is empty.
  • Two pads ([1, 2]): returns 1.
  • Big first jump ([5, 1, 1, 1, 1, 1]): returns 1.
  • Example [2, 3, 1, 1, 4]: returns 2 (jump to the 3, then to the end).
  • Zeros in the middle ([2, 3, 0, 1, 4]): returns 2.
  • Unreachable input ([1, 0, 2]): the problem excludes it, but the code returns 2 instead of reporting failure, because it never checks reachability.
  • All ones ([1, 1, 1, 1]): returns 3.

Common mistakes

  • Forgetting return hops after the loop, so the function returns None.
  • Looping over the last pad too, which counts one extra jump whenever the last pad ends a wave ([2, 3, 1, 1, 4] would give 3).
  • Updating end before reading far for the current pad, which loses the reach of the pad that ends the wave.
  • Taking the jump that goes farthest from the current pad. The right choice is the pad in the wave whose reach goes farthest, which the far variable captures.
Your turn: it may be impossible

The last pad is no longer guaranteed to be reachable. Return the fewest jumps, or -1 if it cannot be reached. For [3, 2, 1, 0, 4] the answer is -1. Describe your approach, then write it if you like.

Compare with our answer

The same waves apply, with one extra test: if far has not moved past the current pad, there is no way forward.

def jump_or_minus1(pads):
    hops, end, far = 0, 0, 0
    for i in range(len(pads) - 1):
        far = max(far, i + pads[i])
        if far <= i:                    # stuck: nothing reaches past pad i
            return -1
        if i == end:
            hops += 1
            end = far
    return hops

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

A strong answer mentions: the wave end and farthest reach, failing when far does not extend past the current pad, returning hops at the end, and handling the one-pad case.

Check what stuck

1. A frog crosses n lily pads, and from pad i it can jump any distance up to lim[i]. The far bank is always reachable. You want the fewest jumps for n up to 10,000. Which approach fits best?

2. A learner deletes the last line, return hops. What does [2, 3, 1, 1, 4] give?

3. A learner changes the loop to for i in range(len(pads)): and keeps return hops. What does [2, 3, 1, 1, 4] give?

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