Jump Game II: Fewest Jumps to the End with Greedy Level-by-Level BFS

Problem

You start at index 0 of a list of non-negative integers, where each value is the longest jump allowed from that index. Return the minimum number of jumps to reach the last index. You may assume the last index is reachable.

This is widely known as LeetCode 45, “Jump Game II”. It extends Jump Game.

Assume up to 10,000 values, each up to 1,000.

Examples

[3, 1, 4, 1, 1, 1, 2]   -> 2   (0 -> 2 -> 6)
[1, 1, 1, 1]            -> 3
[4, 1, 1, 1, 1]         -> 1
[7]                     -> 0   (already at the end)

Approach 1: dynamic programming

fewest[i] = minimum jumps to reach index i; each index relaxes everything in its range.

def jump_dp(nums):
    INF = float("inf")
    fewest = [INF] * len(nums)
    fewest[0] = 0
    for i in range(len(nums)):
        for step in range(1, nums[i] + 1):
            if i + step < len(nums):
                fewest[i + step] = min(fewest[i + step], fewest[i] + 1)
    return fewest[-1]

O(n * maximum jump) time, up to O(n^2).

Approach 2: optimal, greedy BFS by ranges

Why it works

Indices reachable in exactly k jumps form a contiguous block, because reachable sets are prefixes (see Jump Game). The block for k + 1 jumps starts just after the block for k and ends at the furthest i + nums[i] over the block for k. So you can walk the array once and count block boundaries, which is BFS without a queue.

Template

jumps = 0; current_end = 0; furthest = 0
for i in 0 .. n-2:                       # no jump needed from the last index
    furthest = max(furthest, i + nums[i])
    if i == current_end:                 # finished the current level
        jumps += 1
        current_end = furthest
        if current_end >= n - 1: break
return jumps

Python solution

def jump(nums):
    jumps = current_end = furthest = 0
    for i in range(len(nums) - 1):
        furthest = max(furthest, i + nums[i])
        if i == current_end:
            jumps += 1
            current_end = furthest
            if current_end >= len(nums) - 1:
                break
    return jumps

Trace for [3, 1, 4, 1, 1, 1, 2]: level 0 is index 0, which reaches up to 3. Level 1 is indices 1..3, the furthest reach is 2 + 4 = 6, the last index. Two jumps.

Complexity

O(n) time, O(1) space.

Tests

for fn in (jump, jump_dp):
    assert fn([3, 1, 4, 1, 1, 1, 2]) == 2
    assert fn([1, 1, 1, 1]) == 3
    assert fn([4, 1, 1, 1, 1]) == 1
    assert fn([7]) == 0                      # single element
    assert fn([1, 2]) == 1
    assert fn([2, 3, 0, 1, 4]) == 2           # 0 -> 1 -> 4

import random
random.seed(27)
tested = 0
while tested < 150:
    a = [random.randint(0, 4) for _ in range(random.randint(1, 10))]
    if jump_dp(a) == float("inf"):
        continue                              # the problem guarantees reachability
    assert jump(a) == jump_dp(a)
    tested += 1

Edge cases and pitfalls

• Looping to the last index can add an extra jump when i == current_end at the very end; stop at n - 2.
• Greedy by largest value (always jumping as far as possible) is wrong: the best next index is the one whose range reaches furthest, not the one furthest away.
• Single element needs 0 jumps.
• Unreachable end. Not possible under the problem’s guarantee; if it were, detect furthest <= i at a level end and return -1.

Where this shows up in data engineering

There is no direct pipeline use. The transferable technique is BFS without a queue: when the nodes reachable at each level form a contiguous range, you can count levels by tracking range boundaries in a single pass.