#45 Jump Game II
the problem
In plain words
Same jumps as Jump Game, but now the last index is guaranteed to be reachable. Return the fewest jumps needed to reach it.
in nums = [2,3,1,1,4]
out 2
0 → 1 → 4.
in nums = [2,3,0,1,4]
out 2
- 1 ≤ nums.length ≤ 10⁴
- 0 ≤ nums[i] ≤ 1000
- The last index is reachable
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternGreedy furthest reachBFS shortest path (unweighted)
Indices reachable in exactly k jumps form a contiguous block. That's BFS by levels with no queue: end closes the current level, and farthest builds the next.
solutions
From brute force to optimal
minFrom(i) = 1 + min over every jump of minFrom(i + step).
- Base case: i ≥ n − 1 → 0.
- Try every step 1..nums[i] and keep the best.
It explores every path, and there can be exponentially many.
Recursion depth.
class Solution { public int jump(int[] nums) { return minFrom(nums, 0); } private int minFrom(int[] nums, int i) { if (i >= nums.length - 1) return 0; int best = Integer.MAX_VALUE; for (int step = 1; step <= nums[i]; step++) { int rest = minFrom(nums, i + step); if (rest != Integer.MAX_VALUE) best = Math.min(best, rest + 1); } return best; // MAX_VALUE means "can't finish from here" }}dp[j] = min(dp[j], dp[i] + 1) for every j that i can reach.
- dp[0] = 0, others = ∞.
- For each i, relax every j in (i, i + nums[i]].
Each index may relax up to n later indices.
The dp array.
class Solution { public int jump(int[] nums) { int n = nums.length; int[] dp = new int[n]; // dp[i]: fewest jumps to land on i Arrays.fill(dp, Integer.MAX_VALUE); dp[0] = 0; for (int i = 0; i < n; i++) { if (dp[i] == Integer.MAX_VALUE) continue; for (int j = i + 1; j <= Math.min(n - 1, i + nums[i]); j++) { dp[j] = Math.min(dp[j], dp[i] + 1); } } return dp[n - 1]; }}Scan the current level, tracking the farthest index the next jump can reach. When i hits the level's end, count a jump.
- jumps = end = farthest = 0.
- For i in [0, n−2]: farthest = max(farthest, i + nums[i]).
- If i == end: jumps++, end = farthest.
Each index is visited once.
Three integers.
class Solution { public int jump(int[] nums) { int jumps = 0, end = 0, farthest = 0; for (int i = 0; i < nums.length - 1; i++) { farthest = Math.max(farthest, i + nums[i]); if (i == end) { // reached the edge of the current jump's range jumps++; // so we must take another jump... end = farthest; // ...and the next range reaches farthest } } return jumps; }}Dry run
in the room
How to say it in the interview
talk track
- Say: "This is shortest path in an unweighted graph, so BFS. The levels are contiguous ranges, so two integers replace the queue."
- Explain why the loop stops at n − 2: landing on the last index needs no further jump.
traps
- Looping to n − 1 counts an extra jump when
endequals the last index. - Setting
end = farthestbefore folding ini + nums[i]misses the current index's reach.
what they ask next
Follow-ups
What if the end might be unreachable?
Inside the boundary check, if farthest == i (no progress), return −1.
before you submit
Edge cases to test
- [0] → 0 jumps: you are already at the end.
- [4, 1, 1, 1, 1] → 1: the first jump lands exactly on the end.
- [1, 1, 1, 1] → 3: every jump is forced.
practise next
Similar problems
- #55Jump GameMediumin Greedy
- #127Word LadderHardin Graphs