Free lesson · DSA Mastery - Interview Prep, End to End

Jump Game II

Hard9 min readdsagreedy

Jump Game II

Jump Game II opens the jump-problem sub-group and marks where greedy decisively beats dynamic programming: given an array where each value is the maximum jump length from that index, find the minimum number of jumps to reach the last index. The greedy tracks, in a single pass, the farthest index reachable within the current number of jumps and the farthest reachable overall, incrementing the jump count each time you exhaust the current reach - an O(n) sweep that replaces the obvious O(n²) DP. It is the canonical staying-ahead argument: greedy's reachable frontier is never behind any other strategy's. We present the O(n²) DP (baseline) and the BFS-layers greedy sweep (canonical).

The insight: think of the jumps as BFS "levels." From the start, one jump reaches some range of indices; from anywhere in that range, two jumps reach a further range; and so on. The minimum number of jumps to reach the end is the level at which the end first becomes reachable. You don't need to track each index - only the boundary of the current level (currentEnd) and the farthest index any position in this level can reach (farthest). When your scan passes currentEnd, you've used up the current level's reach, so increment the jump count and extend the boundary to farthest.

The 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. In other words, if you are at nums[i], you can jump to any nums[i + j] where 0 <= j <= nums[i] and i + j < n.

Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

Example 1:

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

Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index. Two jumps.

Example 2:

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

Constraints:

• 1 <= nums.length <= 10^4
• 0 <= nums[i] <= 1000
• It's guaranteed that you can reach nums[n - 1].

Approaches Overview

The DP computes jumps[i] = minimum jumps to reach index i by checking all positions that can jump to i - O(n²). The greedy reframes jumps as BFS levels: maintain currentEnd (the farthest index reachable with the jumps taken so far) and farthest (the farthest reachable by jumping from anywhere up to currentEnd). Scanning left to right, when index reaches currentEnd, increment jumps and set currentEnd = farthest. This single O(n) pass finds the minimum.

Approach 1: Dynamic Programming - Baseline

The Idea

Let jumps[i] be the minimum jumps to reach index i, initialized to infinity except jumps[0] = 0. For each i, for each reachable j in [i+1, i+nums[i]], relax jumps[j] = min(jumps[j], jumps[i] + 1). The answer is jumps[n-1]. Correct but O(n²) because each index scans its whole jump range.

Complexity

Time: O(n²) - each index relaxes up to nums[i] successors. Space: O(n) for the DP array.

Approach 2: Greedy BFS-Layer Sweep - Canonical

The Idea

Track jumps (count so far), currentEnd (farthest index reachable using jumps jumps), and farthest (farthest index reachable by jumping from any index in [0, currentEnd]). Scan i from 0 to n-2: update farthest = max(farthest, i + nums[i]). When i == currentEnd, you've reached the edge of the current jump level - increment jumps and set currentEnd = farthest. Stop early if currentEnd >= n-1. The final jumps is the minimum.

Logic Flowchart

graph TD
    A["jumps = 0, currentEnd = 0, farthest = 0"] --> B["for i = 0 to n-2"]
    B --> C["farthest = max(farthest, i + nums[i])"]
    C --> D{"i == currentEnd? (edge of current level)"}
    D -->|Yes| E["jumps++; currentEnd = farthest"]
    D -->|No| B
    E --> F{"currentEnd >= n-1?"}
    F -->|Yes| G["return jumps (end reachable)"]
    F -->|No| B
    B --> H["return jumps"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style D fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style G fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style H fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the jump game greedy. Scanning left to right, it tracks the farthest reachable index; each time the scan reaches the current level's edge, it spends a jump and extends the edge to the farthest, stopping when the end is reachable.

Code

public static int jump(int[] nums) {
    int n = nums.length;
    int jumps = 0, currentEnd = 0, farthest = 0;
    for (int i = 0; i < n - 1; i++) {            // no need to act on the last index
        farthest = Math.max(farthest, i + nums[i]);  // best reach from this level
        if (i == currentEnd) {                   // exhausted current jump's reach
            jumps++;                             // must take another jump
            currentEnd = farthest;               // new level boundary
            if (currentEnd >= n - 1) break;      // end reachable
        }
    }
    return jumps;
}

// Usage:
// jump([2,3,1,1,4]) -> 2
// jump([2,3,0,1,4]) -> 2

This Java code scans the array tracking the farthest reachable index; each time the scan index meets the current level boundary it increments the jump count and advances the boundary to the farthest, stopping once the end is within reach.

Step-by-Step Walkthrough

A frame-by-frame trace on nums = [2,3,1,1,4]:

graph LR
    F0["i=0: farthest=max(0,0+2)=2. i==currentEnd(0) → jumps=1, currentEnd=2"]
    F1["i=1: farthest=max(2,1+3)=4. i != currentEnd(2)"]
    F2["i=2: farthest=max(4,2+1)=4. i==currentEnd(2) → jumps=2, currentEnd=4"]
    F3["currentEnd 4 >= n-1=4 → stop. jumps=2"]
    F0 --> F1 --> F2 --> F3

    style F0 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F1 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F2 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9

This walkthrough runs the jump game. The first level reaches index two; within it, index one can reach index four, so a second jump extends the boundary to four, the last index, giving two jumps.

Result: 2.

Complexity

Time: O(n) - a single pass. Space: O(1).

Complexity Comparison

The greedy replaces the O(n²) DP with a single O(n) pass by recognizing that minimum jumps equals the number of BFS levels to reach the end. You never need per-index jump counts - only the boundary of the current reachable range and the farthest the next jump can extend it. This is where greedy decisively wins over DP, and the staying-ahead argument proves it optimal.

Variations & Follow-ups

Why does counting BFS "levels" give the minimum number of jumps?

Model reachability as a breadth-first search: level 0 is the start index; level 1 is every index reachable in one jump from the start; level 2 is every index reachable in one jump from any level-1 index; and so on. By BFS's defining property, the level at which an index first appears is the minimum number of jumps to reach it - BFS explores all positions reachable in k jumps before any requiring k+1. So the answer is the level number at which the last index first becomes reachable. The greedy computes exactly this without an explicit queue: currentEnd marks the right boundary of the current level (the farthest index reachable with jumps jumps), and farthest accumulates the right boundary of the next level (the farthest reachable by jumping from anywhere in the current level). Crossing currentEnd means moving to the next level, so jumps++. It's BFS compressed into two integers because each level is a contiguous range of indices, not a scattered set.

Why are the reachable indices at each level a contiguous range, and why does that matter?

From the start, one jump reaches indices [1, nums[0]] - a contiguous range, because you can jump any distance from 1 up to nums[0]. From that whole range, two jumps reach [currentEnd+1, farthest] where farthest is the maximum of i + nums[i] over the range - and this is again contiguous, because every index between the old boundary and the new farthest is reachable (you can always reach an intermediate index by jumping slightly less far). This contiguity is what collapses BFS from tracking a set of indices to tracking a single right boundary. You never need a queue or a visited array; the level is fully described by its rightmost reachable index. Without contiguity (e.g., if jumps could skip to scattered positions), you'd need a real BFS. The forward-jump structure guarantees it, which is the special property that makes the O(1)-space greedy possible.

Why is the greedy's reachable frontier never behind any other strategy's (the staying-ahead argument)?

The correctness of "always extend to the farthest reachable" rests on a staying-ahead invariant: after processing the first k levels, the greedy's currentEnd is at least as large as the farthest index any sequence of k jumps could reach. Proof by induction: at level 1, greedy reaches nums[0], the maximum possible in one jump, so it's not behind. Assume greedy's reach after k jumps is maximal; then for level k+1, greedy considers every index up to its (maximal) currentEnd and takes the farthest i + nums[i] among them - and since any competing strategy's k-jump reach is <= greedy's, the competitor's (k+1)-th jump starts no farther than where greedy could start, so the competitor's reach is <= greedy's farthest. Thus greedy stays ahead at every level, so it reaches the end in no more levels (jumps) than anyone else. "Never behind at any step" implies "wins at the end" - the signature staying-ahead structure of jump and reach problems.

Why does the loop stop at n-2 and increment jumps when reaching currentEnd?

The loop runs i only to n-2 because you never need to jump from the last index - reaching it is the goal, and acting on it would over-count. Within the loop, farthest is updated at every index (accumulating the best reach of the current level), but jumps increments only when i == currentEnd - the moment you stand at the current level's right edge and must commit another jump to go further. At that instant, the next level's boundary is whatever farthest has accumulated, so currentEnd = farthest. The early break when currentEnd >= n-1 returns as soon as the end is within the current level, avoiding extra iterations. A subtle correctness point: because the problem guarantees the end is reachable, farthest always advances past currentEnd before the scan would stall, so jumps counts exactly the levels needed. Incrementing at the wrong time - say, on every index, or after the last index - is the classic bug; the increment belongs precisely at the level boundary.

What about edge cases?

• Single element (n == 1): The loop doesn't run; 0 jumps (already at the end).
• All reachable in one jump (nums[0] >= n-1): farthest covers the end on the first level; returns 1.
• Zeros in the middle (Example 2: [2,3,0,1,4]): The greedy jumps over the 0 by reaching past it from an earlier index.
• Large jump values: farthest may exceed n-1; the early break handles it.
• Guaranteed reachable: No need to detect failure; the constraint ensures the end is always reached.

Common Interview Pitfalls

• Incrementing jumps on every index. Increment only at the level boundary (i == currentEnd), not per step.
• Looping to n-1. Stop at n-2; jumping from the last index over-counts.
• Confusing currentEnd and farthest. currentEnd is the committed level's edge; farthest is the next level's reach being accumulated.
• Using O(n²) DP under tight constraints. The greedy O(n) sweep is expected; DP may be too slow at scale.

Why This Topic Matters

Jump Game II is where greedy decisively beats DP: minimum jumps equals BFS levels, computed in one O(n) pass by tracking the current level's edge (currentEnd) and the next level's farthest reach (farthest). It teaches the canonical staying-ahead argument - greedy's frontier is never behind - and the reachable-range contiguity that compresses BFS into two integers.

The next topic, Jump Game, is the simpler reachability question underneath: can you reach the last index at all (not in how few jumps)? The greedy tracks a single value - the farthest index reachable so far - scanning left to right and failing if you ever stand on an index beyond that reach; if the frontier ever covers the last index, you succeed. It distills the reach-tracking idea to its essence (one variable, one pass) and is the natural foundation the minimum-jumps version builds on, even though it appears second here.

Back to DSA Mastery - Interview Prep, End to End