Jump Game II — The Creek Crossing Sprint

Boss 3: The Creek Crossing Sprint

Boss 2 asked whether you can cross. This boss asks for the minimum number of jumps, and it's where naive greed publicly embarrasses itself. Grabbing the highest-power stone at every step, the "obvious" greedy, gives wrong answers. The correct greedy is choosing something subtler: not the springiest stone, but the stone that extends your future reach the most. And the cleanest way to see it is as BFS in disguise.

The story

Your hiking buddy looks at the creek you just crossed and says: "Bet you can't do it in two."

stone:    0    1    2    3    4
power:    2    3    1    1    4

Greedy-by-power says: stone 0 has power 2, and stone 2 has... wait. From stone 0 you can land on stone 1 (power 3) or stone 2 (power 1). The springier landing is stone 1. From stone 1, power 3 reaches the far bank. Two jumps: 0 → 1 → 4.

But notice what made stone 1 right. Not its spring for its own sake, but that landing there opens the farthest next window. Choosing landings by raw power alone can strand you; choosing by "how far does this landing let me see" is the correct greed. Now let's make that mechanical, without evaluating candidate landings one by one.

The problem, dressed up properly

Given an array nums where nums[i] is the maximum jump length from index i, return the minimum number of jumps to reach the last index. Test cases guarantee you can reach it.

LeetCode 45. The guarantee matters: no stranded check needed today, Boss 2 already taught you how anyway.

The naive attempt

BFS, honestly and literally. Each stone is a node, each allowed jump an edge, minimum jumps = shortest path. Dungeon 11's bread and butter:

from collections import deque
 
def min_jumps(nums):
    n = len(nums)
    dist = {0: 0}
    q = deque([0])
    while q:
        i = q.popleft()
        if i == n - 1:
            return dist[i]
        for step in range(1, nums[i] + 1):
            j = i + step
            if j < n and j not in dist:
                dist[j] = dist[i] + 1
                q.append(j)

Correct, and O(n²) edges in the worst case. But here's the thing worth noticing: BFS explores in layers. Layer 0 is stone 0. Layer 1 is everything one jump away. Layer 2 is everything two jumps away. On a line, each layer is just a contiguous window of indices. And a window needs two integers, not a queue.

The weapon: ride the wave

Keep two markers while walking the stones:

• cur_end — the right edge of the window reachable with the current number of jumps
• farthest — the right edge of the next window, fed by every stone walked so far

Walk stone by stone, growing farthest exactly like Boss 2. When your walk hits cur_end, you've exhausted the current wave: everything past this point costs one more jump. So increment the jump counter and let the next wave begin: cur_end = farthest.

You never decide which stone to jump from. The wave holds every option at once, and the best option is whichever stone pushed farthest the most. The choice makes itself.

def min_jumps(nums: list[int]) -> int:
    jumps = 0
    cur_end = 0        # edge of the current jump's window
    farthest = 0       # edge of the next jump's window
    for i in range(len(nums) - 1):   # note: last stone excluded
        farthest = max(farthest, i + nums[i])
        if i == cur_end:             # walked off the wave's edge
            jumps += 1
            cur_end = farthest
    return jumps

BFS with the queue compressed into two integers. Same layers, same answer, O(1) space.

Watching it work

[2, 3, 1, 1, 4]:

i  power  farthest            wave edge check
0  2      max(0, 0+2) = 2     i == cur_end(0) → jumps=1, cur_end=2
1  3      max(2, 1+3) = 4     no
2  1      max(4, 2+1) = 4     i == cur_end(2) → jumps=2, cur_end=4
3  1      max(4, 3+1) = 4     no
loop ends (last stone excluded)

Answer: 2. The waves were [0], then stones 1 to 2, then stones 3 to 4. The far bank sits in wave 2, so two jumps, and nobody ever compared candidate landings head-to-head.

Gotchas

1. Greedy by jump length. "Always jump as far as you can" fails on the very first example: from stone 0 in [2, 3, 1, 1, 4], the full-distance jump lands on stone 2 (power 1), forcing 0 → 2 → 3 → 4, three jumps instead of two. The distance of the jump is irrelevant. The reach of the landing is everything, and the wave trick maximizes it without comparing candidates one by one.

2. Incrementing jumps per stone instead of per wave. The whole point is that walking within a window is free, you're considering landing spots, not jumping to each. Jumps increment only at i == cur_end.

3. Forgetting the single-stone creek. nums = [0]: already on the far bank, zero jumps. The loop range range(len(nums) - 1) is empty and returns 0 gracefully. A version that loops all stones returns 1. Test it.

4. Missing the BFS connection. Not a correctness bug, an understanding bug. If you memorize this as "two mysterious pointers," it evaporates in interviews. Remember it as BFS layers on a line, and you can re-derive it from scratch in a minute.

Complexity

One pass, three integers.

Time: O(n). Space: O(1).

Boss down. XP gained.

Two jumps, stopwatch clicked, buddy pays for lunch. The creek has nothing left to teach.

What you walked away with:

• Min-steps on a line is BFS in layers, and contiguous layers compress to two integers
• The right greedy criterion is future reach, not local appeal, and the wave computes it implicitly
• i == cur_end marks the exact moment another jump becomes unavoidable
• Loop over every stone except the last, or pay an off-by-one on arrival

Next up: Boss 4 — The Milk Run. A circular delivery route, fuel cans at every stop, and a truck that might not make the loop. One elegant theorem about failure, and the start point reveals itself.