☕ DSA Java Articles

Topics › Greedy Algorithms › Medium/Hard

Jump Game II

Medium TUF ID 595 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You start at index 0 of an array nums. From index i you may jump forward by any number of steps from 1 up to nums[i]. Return the minimum number of jumps needed to reach the last index. LeetCode guarantees the last index is reachable; the GeeksforGeeks variant asks for -1 when it is not, and the code below handles both by returning -1 for an unreachable end.

Constraints: 1 ≤ n ≤ 10^4, 0 ≤ nums[i] ≤ 1000. Reaches i + nums[i] stay far below the int limit.

Example 1

nums = [2, 3, 1, 1, 4]
answer = 2          // 0 -> 1 (jump 1), then 1 -> 4 (jump 3)

Example 2

nums = [1, 1, 1, 1]
answer = 3          // every jump is forced to be exactly one step

Approach 1: Brute force, recursion over every jump

Intuition. The fewest jumps from index i is 0 if i is already the last index; otherwise it is one jump plus the fewest jumps from the best landing spot in i + 1 .. i + nums[i]. Write that down as a recursion. A spot from which the end cannot be reached returns a sentinel INF (here Integer.MAX_VALUE, stored in the constant INF), and we never add 1 to INF.

Algorithm.

  1. minJumpsFrom(i): if i ≥ n - 1, return 0.
  2. For each landing index j from i + 1 to min(n - 1, i + nums[i]), compute minJumpsFrom(j); if it is not INF, keep the minimum of sub + 1.
  3. Return the minimum (still INF if no landing spot works). The wrapper turns INF into -1.
static int bruteForce(int[] nums) {
    int best = minJumpsFrom(nums, 0);
    return best == INF ? -1 : best;
}

static int minJumpsFrom(int[] nums, int i) {
    if (i >= nums.length - 1) return 0;
    int best = INF;
    int far = Math.min(nums.length - 1, i + nums[i]);
    for (int j = i + 1; j <= far; j++) {
        int sub = minJumpsFrom(nums, j);
        if (sub != INF) best = Math.min(best, sub + 1);
    }
    return best;
}

Complexity. Time exponential: the same index is solved again for every route that reaches it, and there can be about 2^n routes. Space O(n) for the recursion depth.

Approach 2: Better, dynamic programming from the right

Intuition. minJumpsFrom(j) does not depend on how we reached j, so compute it once per index. Fill dp[i] from right to left; when we handle i, every dp[j] with j > i is already final.

Algorithm.

  1. dp[n - 1] = 0.
  2. For i from n - 2 down to 0: dp[i] = INF, then for each j in (i, min(n - 1, i + nums[i])] with dp[j] != INF, set dp[i] = min(dp[i], dp[j] + 1).
  3. Return dp[0], or -1 if it is INF.
static int better(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    dp[n - 1] = 0;
    for (int i = n - 2; i >= 0; i--) {
        dp[i] = INF;
        int far = Math.min(n - 1, i + nums[i]);
        for (int j = i + 1; j <= far; j++) {
            if (dp[j] != INF) dp[i] = Math.min(dp[i], dp[j] + 1);
        }
    }
    return dp[0] == INF ? -1 : dp[0];
}

Complexity. Time O(n^2) in the worst case because each index may scan up to n landing spots. Space O(n) for dp.

Approach 3: Optimal, greedy breadth-first levels

Intuition. Think of the jumps as a breadth-first search. Level 0 is just index 0. Level k is the set of indices whose minimum jump count is exactly k. From Jump Game I we know that the indices reachable with at most k jumps form a prefix [0, R_k], because you can always jump shorter. So each level is a contiguous window: level k is (R_{k-1}, R_k].

That makes BFS trivial. Keep the current window [l, r]. The next window starts at r + 1 and ends at the farthest index any member of the current window can reach, max(i + nums[i]) for i in [l, r]. We only need to scan the current window: indices from earlier windows already had their reach counted when r was computed. Each time we move to the next window we have spent one more jump; the first window that contains the last index gives the answer.

If a window cannot push past its own right end (farthest == r), no index beyond r is reachable at all, so we return -1.

Algorithm.

  1. jumps = 0, l = r = 0.
  2. While r < n - 1:
    • farthest = max(i + nums[i]) over i in [l, r] (starting from r).
    • If farthest == r, return -1.
    • l = r + 1, r = farthest, jumps++.
  3. Return jumps.
static int optimal(int[] nums) {
    int n = nums.length, jumps = 0, l = 0, r = 0;
    while (r < n - 1) {
        int farthest = r;
        for (int i = l; i <= r; i++) farthest = Math.max(farthest, i + nums[i]);
        if (farthest == r) return -1;           // this level cannot push past r: stuck
        l = r + 1;
        r = farthest;
        jumps++;
    }
    return jumps;
}

Dry run on nums = [2, 3, 1, 1, 4]:

jumps window [l, r] reaches from the window farthest
0 [0, 0] 0 + 2 = 2 2
1 [1, 2] 1 + 3 = 4, 2 + 1 = 3 4
2 [3, 4] window contains index 4, loop stops  

The answer is 2. On [3, 2, 1, 0, 4] the second window is [1, 3], whose best reach is 3, equal to r, so the method returns -1.

Complexity. Time O(n): the windows are disjoint and every index is scanned once. Space O(1).

The same idea is often written as a single loop with a currentEnd and a farthest variable, incrementing jumps whenever i reaches currentEnd. It is equivalent; the window form just makes the BFS levels visible.

Edge cases and pitfalls