Minimum jumps to reach the end

Minimum jumps is dynamic programming disguised as graph reachability: from index i you can land on any index in [i+1, i+jumps[i]], and you want the fewest edges to travel from index 0 to index n-1 in this implicit DAG. Each index's minimum jump count depends only on the minimum jump counts of indices that can reach it — overlapping subproblems plus optimal substructure.

Recognize the pattern

• phrase “minimum number of jumps/steps/moves to reach the end/target” over an array where each cell caps how far you may move forward
• the reachable set from a position is a contiguous range, not one fixed successor — this range structure is what enables a greedy “farthest reach” solution
• a 0 in the array blocks passage through that cell, hinting some inputs are unreachable (not this problem’s guarantee, but check for it)
• sibling problem “Jump Game” asks only whether the end is reachable (boolean); this one counts the minimum jumps

Brute force → optimal

Brute force: from index i, recursively try every jump length 1..jumps[i] and take 1 + min(jumps(i+k)) over reachable i+k. The same suffix index gets re-explored via many different paths — exponential blow-up, O(2^n) time worst case, O(n) stack space.

DP (bottom-up): let dp[i] = minimum jumps from index 0 to reach index i. dp[0]=0; for each i, scan every j<i with j+jumps[j]≥i and take dp[i]=min(dp[j]+1). No subproblem is solved twice, but the scan makes it O(n²) time, O(n) space.

Optimal (greedy, BFS by levels): think of jump count as BFS depth. Walk the array once tracking currentEnd (farthest index reachable using the jumps taken so far) and farthest (farthest index reachable by extending one more jump from anywhere in the current level). When the walk reaches currentEnd, the current level is exhausted, so increment jumps and set currentEnd=farthest. This is O(n) time, O(1) space — every index is visited once and the range never needs to be rescanned.

Complexity, derived

DP: the outer loop runs n times; the inner scan over previous indices runs up to i times — sum 1+2+...+(n-1) = n(n-1)/2 comparisons, so O(n²) time. Space is one array of size n for dp, O(n).

Greedy: the single pointer i advances from 0 to n-1 exactly once, and at each i we do O(1) work updating farthest = max(farthest, i+jumps[i]). Total work is a single pass: O(n) time. Only three scalars (jumps, currentEnd, farthest) are kept, so O(1) extra space.

Traced example

Input [2,1,1,1,4], expected output 3.

Reading the walk: at i=0, i==currentEnd (0), so jump 1 is taken and currentEnd becomes 2. At i=1, i≠currentEnd (1≠2), so no jump yet, but farthest is refreshed. At i=2, i==currentEnd (2), so jump 2 is taken and currentEnd becomes 3 — not 4; index 4 is not reached yet. At i=3, i==currentEnd (3), so jump 3 is taken and currentEnd becomes 4, which now covers the last index, so the loop breaks immediately. Result: 3 jumps, matching the example — one jump is taken at each of i=0, 2, 3, never at i=1.

Pitfalls

• updating currentEnd too early (inside the same step you compute farthest) causes an off-by-one under- or over-count of jumps
• forgetting to stop as soon as currentEnd ≥ n-1, which can walk past the end or trigger an extra unnecessary jump increment
• not handling a 0 that leaves farthest stuck at or behind i, meaning no forward progress is possible — must be detected as “unreachable” rather than looping forever (this problem guarantees reachability, but real inputs may not)
• using the O(n²) DP on inputs near n=10⁴ — 10⁸ operations will time out

When to use / when not

Use the greedy BFS-by-levels approach whenever the reachable set from a position is a contiguous prefix/suffix range and you only need the minimum count — it dominates the DP in both time and space with no loss of correctness. Fall back to the O(n²) DP (or a full DP table) only if you also need to reconstruct the exact sequence of indices visited, since the greedy version discards path history by design (though it can be extended by recording a parent pointer at each level). Compare against plain BFS on an explicit graph: BFS with a queue is the general tool for weighted/irregular adjacency, but here it would still cost O(n²) edges in the worst case (each index can reach up to n others) unless you exploit the range structure the way the greedy method does — the greedy approach is really BFS with the queue collapsed into two pointers.

Java

public int minJumps(int[] jumps) {
    int n = jumps.length;
    if (n <= 1) return 0;
    int jumpCount = 0, currentEnd = 0, farthest = 0;
    for (int i = 0; i < n - 1; i++) {
        farthest = Math.max(farthest, i + jumps[i]);
        if (i == currentEnd) {
            jumpCount++;
            currentEnd = farthest;
            if (currentEnd >= n - 1) break;
        }
    }
    return jumpCount;
}

Takeaways

• a contiguous reachable range per step is the signal that a greedy “farthest reach” pass can replace an O(n²) DP with O(n)
• the greedy method is BFS with levels tracked by two pointers instead of an explicit queue
• DP is still the right first draft when the reachable set is irregular or you need to reconstruct the path

Recall: why does incrementing jumpCount only when i == currentEnd (rather than at every step) still give the exact minimum?

Pattern derived from classic “Jump Game II” formulation (Educative/LeetCode-style DP & Greedy course material); complexity and trace verified by hand.