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

class Solution:
    def jump(self, 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

The greedy-choice property (why we never pick a specific landing spot): Group indices by how many jumps they need: layer k is the contiguous range of indices reachable in exactly k jumps. The key fact is that these layers are contiguous ranges, and the range reachable in k+1 jumps is exactly [end_k + 1, max over the layer-k range of (i + nums[i])]. So to compute the next layer you only need the farthest reach achievable from anywhere in the current layer — never which index you jumped from. Extending to the maximum reach is optimal because any index the next layer can touch is covered by that single farthest value, and reaching less far could only need more jumps, never fewer. This is breadth-first search where each “level” is an interval, giving the minimum jump count directly (BFS finds shortest paths in an unweighted graph).

We iterate to n-2 (never 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

class Solution:
    def jump(self, 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.