Jump Game II (LeetCode 45)

The problem

You stand at index 0 of an array nums. From index i you may jump forward by any distance from 1 up to nums[i]. Return the minimum number of jumps to reach the last index. The input guarantees the end is reachable.

Input:  nums = [2, 3, 1, 1, 4]
Output: 2

Jump from index 0 to index 1 (one step), then from index 1 jump 3 steps to index 4.

How to think about it

Start with brute force. Try every jump length from every index recursively, or run a DP where dp[i] is the fewest jumps to reach i and each index updates everything it can reach. The DP is O(n²) in the worst case, since each index can reach up to n others. That is too slow for n = 10⁴ with big jump values.

The key insight: jumps are BFS levels. With 0 jumps you can stand only at index 0. With 1 jump you can reach any index in [1, nums[0]]. With 2 jumps you can reach anything reachable from that window, and so on. Each “level” is a contiguous window of indices, because if you can reach index k you can also reach everything before it. So you don’t need a queue; you only need the right edge of the current window (end) and the furthest index reachable from inside it (far).

When you walk past the edge, you must jump. Scan left to right, updating far = max(far, i + nums[i]). When i hits end, every index in the current level has been considered, so you take one more jump and the next level ends at far. You never decide which index to jump from; you only count how many windows you pass through.

Which pattern is this? Greedy reach tracking, an implicit BFS. The tell is “minimum number of steps” on an array where each cell says how far you can go.

Approach

1. Set jumps = 0, end = 0 (edge of the current window) and far = 0 (best reach seen).
2. Scan i from 0 to n - 2. You stop before the last index because standing on it needs no further jump.
3. At each i, update far = max(far, i + nums[i]).
4. If i == end, the current window is exhausted: add one jump and set end = far.
5. Return jumps.

Solution

def jump(nums):
    jumps = end = far = 0
    for i in range(len(nums) - 1):       # never jump from the last index
        far = max(far, i + nums[i])      # furthest reach from the current window
        if i == end:                     # window exhausted: must take a jump
            jumps += 1; end = far
    return jumps
# jump([2,3,1,1,4]) -> 2

Dry run

On nums = [2, 3, 1, 1, 4]:

The loop stops before index 4. The answer is 2.

Complexity

• Time: O(n). One pass, constant work per index.
• Space: O(1). Three integers.

Edge cases and pitfalls

• Single element ([0]) returns 0: the loop range is empty.
• Looping to n - 1 instead of n - 2 adds a spurious jump when end lands exactly on the last index.
• Greedily jumping to the furthest index from where you stand is wrong; the right move is counting windows, not picking the biggest jump.
• Unreachable end isn’t possible here, but in a variant you’d detect it when far <= i at a window edge.

Related problems

• Jump Game (LeetCode 55): the yes/no version, tracking only the furthest reach.
• Partition Labels (LeetCode 763): the same “extend the far edge, close the window when you hit it” scan.
• Gas Station (LeetCode 134): another one-pass greedy with a running state that decides when to reset.