Jump Game II

Problem

You are given an integer array nums. You start at index 0, and each nums[i] is the maximum jump length from index i (you may land on any index in i+1 .. i+nums[i]). It is guaranteed you can reach the last index. Return the minimum number of jumps needed to get from index 0 to the last index.

Examples

• nums = [2,3,1,1,4] → 2 — jump 0→1 (length 1), then 1→4 (length 3): two jumps.
• nums = [2,3,0,1,4] → 2 — 0→1, then 1→4, again two jumps.
• nums = [0] → 0 — already at the last index, no jump needed.

Constraints

• 1 <= len(nums) <= 10^4
• 0 <= nums[i] <= 1000
• It is guaranteed you can reach nums[len(nums) - 1].

An O(n) solution is expected; the O(n^2) DP is too slow at the upper bound.

Think about it first

TL;DR

Treat reachable ranges as BFS layers; scan once, and each time you exhaust the current layer take one jump to the farthest reach found — O(n) time, O(1) space.

Approach 1 — Dynamic programming

Let dp[i] be the minimum jumps to reach index i. Initialize dp[0] = 0, everything else inf, and relax forward: from each i you can improve dp[j] for j in i+1 .. i+nums[i].

from typing import List

def jump(nums: List[int]) -> int:
    n = len(nums)
    dp = [float('inf')] * n
    dp[0] = 0
    for i in range(n):
        reach = min(i + nums[i], n - 1)
        for j in range(i + 1, reach + 1):
            if dp[i] + 1 < dp[j]:
                dp[j] = dp[i] + 1
    return int(dp[n - 1])

Complexity: O(n^2) time (each i relaxes up to nums[i] successors), O(n) space. Correct but too slow at n = 10^4 with large jump values.

Approach 2 — Greedy BFS by layers

Group indices by how many jumps they need: layer k is the range of indices reachable in exactly k jumps. These layers are contiguous ranges, and the range reachable in k+1 jumps is [end_k + 1, max over the layer-k range of (i + nums[i])]. To compute the next layer you only need the farthest reach achievable from anywhere in the current layer, not which index you jumped from. Extending to the maximum reach is optimal: any index the next layer can touch is covered by that single farthest value, and reaching less far can only need more jumps, never fewer. This is BFS where each level is an interval, so it yields the minimum jump count directly (BFS finds shortest paths in an unweighted graph).

For nums = [2,3,1,1,4] the layers are:

flowchart LR
  L0["Layer 0<br/>index 0"] --> L1["Layer 1<br/>indices 1-2"] --> L2["Layer 2<br/>indices 3-4"]

Index 4 (the goal) sits in layer 2, so the answer is 2 jumps.

We iterate to n-2 (there is never a need to jump from the last index) and count a jump each time i reaches the end of the current layer.

from typing import List

def jump(nums: List[int]) -> int:
    jumps = 0
    cur_end = 0        # last index of the current BFS layer
    farthest = 0       # farthest index reachable from the current layer
    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        if i == cur_end:      # exhausted this layer -> must jump
            jumps += 1
            cur_end = farthest
    return jumps

Walkthrough on nums = [2,3,1,1,4]:

1. i=0: farthest = max(0, 0+2) = 2. i == cur_end (0) → jumps=1, cur_end=2.
2. i=1: farthest = max(2, 1+3) = 4. i (1) != cur_end (2), no jump.
3. i=2: farthest = max(4, 2+1) = 4. i == cur_end (2) → jumps=2, cur_end=4.
4. Loop stops at i = 3 (n-1 = 4 excluded). cur_end=4 >= last, answer 2.

The two jumps correspond to the two layers: layer 1 covers indices 1..2, layer 2 reaches index 4.

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

Common pitfalls

• Iterating to n-1 instead of n-2. If the loop visits the last index and it happens to equal cur_end, you count one jump too many (a phantom jump from the goal).
• Incrementing jumps on every step instead of only when i == cur_end. The jump count is the number of layers, not the number of indices.
• Confusing this with Jump Game I: there you only ask whether the end is reachable; here you must count the minimum jumps, so the layer boundary logic matters.

Pattern takeaway

Minimum-steps-to-reach problems on “you can advance up to k” arrays are BFS in disguise. Because each layer is a contiguous interval, you replace an explicit queue with two pointers — current layer end and farthest reach — and greedily extend to the farthest reach each time a layer runs out.