Difficulty: MediumGreedy

Jump Game II

Problem in Plain English

Given an array where each element caps how far you can jump forward, find the fewest jumps needed to travel from the first index to the last one. Reaching the end is always possible.

Problem Statement

You are given a 0-indexed array nums where nums[i] is the maximum forward jump length from index i. Starting at index 0, reach index n - 1 in as few jumps as possible.

The test cases guarantee the last index is reachable. For nums = [2, 3, 1, 1, 4] the answer is 2: jump from index 0 to 1, then from 1 to 4.

Constraints

1 <= nums.length <= 10^4
0 <= nums[i] <= 1000
Reaching the last index is always possible.

Examples

Example 1

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

The path 0 -> 1 -> 4 uses two jumps. One jump cannot reach index 4 because nums[0] = 2, so two is the minimum.

Example 2

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

The zero at index 2 is a trap for a path landing there, but 0 -> 1 -> 4 skips it. Index 4 lies beyond the first jump range [1, 2], proving that the two-jump path is optimal.

Example 3

Input: nums = [0]
Output: 0

The first index is already the last index. No move is needed, even though its jump length is zero.

Intuition

A jump length is a maximum, so landing closer can set up a better next jump. In Example 1, jumping straight from index 0 to 2 needs three jumps overall, while landing at 1 reaches index 4 in two. Instead of committing to one landing, keep the whole group of indices reachable with the same minimum jump count. After one jump that group is [1, 2]; either member may launch the next jump. The best reach among them is 1 + 3 = 4, so two jumps suffice.

Approaches

Brute Force DP

Solution Details

Reveal Brute Force DP: intuition, complexity, and code

Intuition

Record the cheapest jump count to every index: an index is reachable from each earlier index whose jump covers the gap, so its price is one more than the cheapest such predecessor. Testing all predecessors is correct but repeats the same reachability checks quadratically.

Step-by-Step Logic

Allocate one minimum-cost entry per index; set the start to zero and all others to infinity. Example 1 starts with dp = [0, inf, inf, inf, inf].
Process destinations from left to right, so every predecessor cost is finalized. For i = 1, predecessor 0 reaches it and sets dp[1] = 1.
For each destination, scan every earlier index and minimize dp[j] + 1 over reachable predecessors that cover the gap. At i = 2, candidates from 0 and 1 are 1 and 2, leaving dp[2] = 1.
Do not stop at a first candidate: complete the predecessor scan. At i = 3, index 0 cannot reach it; indices 1 and 2 both propose 2. At i = 4, indices 1 and 3 propose 2 and 3, so keep 2.
Return the last cost after processing all destinations. Example 1 finishes with [0, 1, 1, 2, 2] and returns 2.

Why It Works

Use induction on the destination index. The start needs zero jumps. Every positive forward path to index i must finish with a jump from some earlier reachable index j satisfying j + nums[j] >= i. The inner loop considers every such predecessor. By induction, dp[j] already gives its minimum cost, so adding one produces the best path ending with that predecessor. Taking the minimum across all predecessors gives exactly the minimum cost for i. Unreachable predecessors remain infinite and are ignored. Zero-length jumps never improve a path and can be omitted. Therefore the final entry is the required minimum.

Dry Run

Brute Force DP: variable states at each step
Destination `i`	Predecessor `j`	Reach `j + nums[j]`	Candidate	`dp[i]` before -> after
start	none	none	none	`dp = [0, inf, inf, inf, inf]`
`1`	`0`	`2`	`0 + 1 = 1`	`inf -> 1`
`2`	`0`	`2`	`0 + 1 = 1`	`inf -> 1`
`2`	`1`	`4`	`1 + 1 = 2`	`1 -> 1`
`3`	`0`	`2`	cannot reach `3`	`inf -> inf`
`3`	`1`	`4`	`1 + 1 = 2`	`inf -> 2`
`3`	`2`	`3`	`1 + 1 = 2`	`2 -> 2`
`4`	`0`	`2`	cannot reach `4`	`inf -> inf`
`4`	`1`	`4`	`1 + 1 = 2`	`inf -> 2`
`4`	`2`	`3`	cannot reach `4`	`2 -> 2`
`4`	`3`	`4`	`2 + 1 = 3`	`2 -> 2`
return	none	none	none	`[0, 1, 1, 2, 2]`, answer `2`

Complexity Analysis

Time Complexity

O(n^2)

Space Complexity

O(n)

For length n, the nested loops test n(n - 1)/2 predecessor pairs even when few jumps are possible. Initialization adds linear work. The only growing auxiliary allocation is the n-entry dp array; loop variables and the returned integer are constant-size. The input is read without mutation, and no recursion or path list is allocated.

Code

Solution.java

1import java.util.Arrays;2
3class Solution {4    public int jump(int[] nums) {5        int n = nums.length;6        int[] dp = new int[n];7        Arrays.fill(dp, Integer.MAX_VALUE);8        dp[0] = 0;9        for (int i = 1; i < n; i++) {10            for (int j = 0; j < i; j++) {11                // Skip infinity before adding one, avoiding integer overflow.12                if (j + nums[j] >= i && dp[j] != Integer.MAX_VALUE) {13                    dp[i] = Math.min(dp[i], dp[j] + 1);14                }15            }16        }17        return dp[n - 1];18    }19}

Hints

Hint 1

Group indices by how many jumps it takes to reach them rather than tracking single paths.

Hint 2

Ask how far the whole current group can collectively reach in one more jump.

Hint 3

Slide a window from each reach frontier to the farthest point it attains and count the slides.

Edge Cases

Single element [0], where zero jumps already stand on the last index.
First element reaching the end directly, as in [5, 1, 1, 1], for an answer of 1.
Zeros inside the array that the window must leap over, as in [2, 3, 0, 1, 4].
All ones force n - 1 jumps; every window advances by exactly one index.
A frontier beyond the final index, as in [1000, 0], still gives one jump and must not trigger an out-of-range scan.

Common Mistakes and Interview Tips

Always landing as far as possible: Example 1 goes 0 -> 2 -> 3 -> 4 in three jumps, while 0 -> 1 -> 4 needs two.
Stopping the loop one window early and undercounting the final jump onto the last index.
Recomputing reachability with overlapping windows, which repeats scans and loses the linear bound.
Incrementing the jump counter for each scanned index instead of once per completed layer.
Applying this loop to an unreachable input without a progress check. That is outside the contract; a stuck frontier would loop forever.
In Java DP, adding one to Integer.MAX_VALUE before checking reachability causes overflow and a false minimum.

Key Takeaway

When every edge costs one, expand the reachable frontier wave by wave instead of pricing individual paths.