Jump Game II

Problem

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0]. Each element nums[i] represents the maximum length of a forward jump from index i. Return the minimum number of jumps to reach nums[n - 1].

Examples

The brute-force approach

BFS level by level. Each level is the set of positions reachable in exactly k jumps. The answer is the level at which you first reach or pass the last index.

from collections import deque
queue = deque([0])
visited = {0}
jumps = 0
while queue:
    for _ in range(len(queue)):
        pos = queue.popleft()
        if pos >= last: return jumps
        for jump in range(1, nums[pos]+1):
            if pos+jump not in visited:
                visited.add(pos+jump)
                queue.append(pos+jump)
    jumps += 1

O(n²) in the worst case and O(n) space for visited set. The greedy range-based approach avoids both.

Spotting the pattern

This is a Greedy problem. The key question to ask yourself:

After a jump lands you somewhere in [left, curEnd], what is the farthest you can reach in the next jump, and when do you decide to make that jump?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.