124.Jump Game II

MediumGreedy · 3/8

Problem

You are given an integer array nums and start at index 0. From index i you may jump to any index i + j where 0 <= j <= nums[i] and i + j < n.

Return the minimum number of jumps needed to reach the last index. The test cases guarantee that the last index is reachable.

Examples

Input:  nums = [2,3,1,1,4]
Output: 2
Explanation: Jump 0 -> 1 (1 step), then 1 -> 4 (3 steps).

Input:  nums = [2,3,0,1,4]
Output: 2
Explanation: Again 0 -> 1 -> 4.

Input:  nums = [0]
Output: 0
Explanation: Already at the last index.

Constraints

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

💡 Key Insight

Think of it as BFS over indices, where "level k" is the set of indices reachable with exactly k jumps. Because reachable sets are contiguous, every level is just a window [l, r]. The next window runs from r + 1 to the farthest i + nums[i] for any i in the current window. Counting windows until one covers n - 1 gives the answer in a single O(n) pass with O(1) memory.

Brute Force Recursion

TimeO(k^n) worst caseSpaceO(n)

Intuition

From index i, try every jump 1..nums[i] and take 1 + the best result from the landing spot. Without caching, the same suffix is solved again and again.

Algorithm

minJumps(i): if i >= n - 1 return 0.
best = INF; for each step in 1..nums[i]: best = min(best, 1 + minJumps(i + step)).
Return best.

Visualization

nums = [2,3,1,1,4]
minJumps(0) = 1 + min(minJumps(1), minJumps(2))
minJumps(1) = 1 + min(minJumps(2), minJumps(3), minJumps(4)=0) = 1
minJumps(2) = 1 + minJumps(3) = 1 + 1 = 2
minJumps(0) = 1 + min(1, 2) = 2

Code

java

class Solution {
    public int jump(int[] nums) {
        return minJumps(nums, 0);
    }

    private int minJumps(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 sub = minJumps(nums, i + step);
            if (sub != Integer.MAX_VALUE) {
                best = Math.min(best, 1 + sub); // guard against dead ends
            }
        }
        return best;
    }
}

Complexity

Time: O(k^n) worst case — k is the maximum jump length; overlapping subproblems explode.
Space: O(n) — recursion depth.

Bottom-Up DP

TimeO(n · k)SpaceO(n)

Intuition

Let dp[i] be the minimum jumps from index i to the end. dp[n - 1] = 0, and dp[i] = 1 + min(dp[i + 1 .. i + nums[i]]). Filling right to left solves each index exactly once.

Algorithm

dp[n - 1] = 0; all others INF.
For i from n - 2 down to 0: for j in i + 1 .. min(n - 1, i + nums[i]), dp[i] = min(dp[i], 1 + dp[j]) when dp[j] is finite.
Return dp[0].

Visualization

i	nums[i]	reachable j	dp[i]
4	4	—	0
3	1	4	1
2	1	3	2
1	3	2, 3, 4	1
0	2	1, 2	2

Code

java

import java.util.Arrays;

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[n - 1] = 0;
        for (int i = n - 2; i >= 0; i--) {
            int furthest = Math.min(n - 1, i + nums[i]);
            for (int j = i + 1; j <= furthest; j++) {
                if (dp[j] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], 1 + dp[j]);
                }
            }
        }
        return dp[0];
    }
}

Complexity

Time: O(n · k) — up to O(n²); each index scans its jump range.
Space: O(n) — the dp array.

Greedy BFS WindowsOptimal

TimeO(n)SpaceO(1).

Intuition

Indices reachable in jumps jumps form a window [l, r]. Scan that window, computing farthest = max(i + nums[i]). The next window is [r + 1, farthest], and it costs one more jump. Repeat until r >= n - 1. Every index is scanned once, so this is linear. A common compact form keeps currentEnd (the end of the window) and increments jumps whenever i reaches it.

Algorithm

jumps = 0, currentEnd = 0, farthest = 0.
For i from 0 to n - 2:
- farthest = max(farthest, i + nums[i]).
- If i == currentEnd: jumps++, currentEnd = farthest (move to the next window).
Return jumps.

Dry Run

flowchart LR
    W0["window 0: [0,0]<br/>farthest = 0 + 2 = 2"] -->|"jump 1"| W1["window 1: [1,2]<br/>farthest = max(1+3, 2+1) = 4"]
    W1 -->|"jump 2"| W2["window 2: [3,4]<br/>contains last index"]
    W2 --> R["return 2"]

nums = [2,3,1,1,4], n - 1 = 4
i=0: farthest=2; i == currentEnd(0) -> jumps=1, currentEnd=2
i=1: farthest=4
i=2: farthest=4; i == currentEnd(2) -> jumps=2, currentEnd=4
i=3: farthest=4  (loop stops before i = 4)
return 2

Code

java

class Solution {
    public int jump(int[] nums) {
        int jumps = 0;
        int currentEnd = 0; // last index reachable with `jumps` jumps
        int farthest = 0;   // last index reachable with `jumps + 1` jumps
        // stop at n - 2: once we are at the last index we need no more jumps
        for (int i = 0; i < nums.length - 1; i++) {
            farthest = Math.max(farthest, i + nums[i]);
            if (i == currentEnd) { // finished scanning this BFS level
                jumps++;
                currentEnd = farthest;
            }
        }
        return jumps;
    }
}

Complexity

Time: O(n) — single pass.
Space: O(1).

Complexity Comparison

Approach	Time	Space
Brute Force Recursion	O(k^n)	O(n)
Bottom-Up DP	O(n · k)	O(n)
Greedy BFS Windows	O(n)	O(1)

Common Pitfalls

Looping to n - 1 inclusive in the greedy version — if currentEnd lands exactly on the last index, you would count an extra jump.
Greedily jumping to the index with the largest nums[i] value instead of the index that reaches farthest (i + nums[i]).
Adding 1 + INF in DP, which overflows to a negative number; guard unreachable entries.
Forgetting the n = 1 case, which must return 0.