Course4all

Jump Game II

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Greedy.

Jump Game II

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].
Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:
  • 0 <= j <= nums[i] and
  • i + j < n
Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

Visual Representation

Index: 0 1 2 3 4 Value: 2 3 1 1 4 Step 1: At index 0 (val 2). Can jump to 1 or 2. Step 2: From index 1 (val 3). Can jump to 4 (Goal!). Total Jumps: 2
Medium

Examples

Input: nums = [2,3,1,1,4]
Output: 2
Jump 1 step from index 0 to 1, then 3 steps to the last index.
Approach 1

Level I: Dynamic Programming (Bottom-Up)

Intuition

Define dp[i] as the minimum jumps to reach the end starting from index i. To find dp[i], we 'look ahead' at all reachable indices j and pick the best one.

Thought Process

  1. dp[i] is the min jumps from index i to n-1.
  2. Base case: dp[n-1] = 0.
  3. Recurrence: dp[i] = 1 + min(dp[j]) for all i < j <= i + nums[i].
  4. Initialize dp with infinity.

Pattern: DAG Shortest Path

⏱ O(N^2)💾 O(N)

Detailed Dry Run

nums = [2, 3, 1, 1, 4]
iRangeBest Nextdp[i]
4--0
3[4]idx 4 (0)1
2[3]idx 3 (1)2
1[2,3,4]idx 4 (0)1
0[1,2]idx 1 (1)2
java
public class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        java.util.Arrays.fill(dp, 10001);
        dp[n - 1] = 0;
        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; j <= Math.min(i + nums[i], n - 1); j++) {
                dp[i] = Math.min(dp[i], 1 + dp[j]);
            }
        }
        return dp[0];
    }
}
Approach 2

Level II: Breadth-First Search (Queue-Based)

Intuition

Each jump can be seen as a 'level' in BFS. Indices reachable in 1 jump are Level 1, indices reachable in 2 jumps are Level 2, etc. Use a queue to traverse until n−1n-1 is reached.

Thought Process

  1. Queue stores (index, levels).
  2. Use visited set to avoid cycles/redundancy.
  3. For each popped index, push all unvisited neighbors i+1…i+nums[i]i+1 \dots i+nums[i].

Pattern: Level-Order Traversal

⏱ O(N^2) worst case, $O(N)$ with optimization.💾 O(N)

Detailed Dry Run

nums = [2, 3, 1, 1, 4] q: [(0,0)]. Pop (0,0). Push (1,1), (2,1). Vis={0,1,2}. Pop (1,1). Push (3,2), (4,2). Reach end! Return 2.
java
public class Solution {
    public int jump(int[] nums) {
        if (nums.length <= 1) return 0;
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{0, 0});
        boolean[] vis = new boolean[nums.length];
        vis[0] = true;
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            for (int j = 1; j <= nums[cur[0]]; j++) {
                int next = cur[0] + j;
                if (next >= nums.length - 1) return cur[1] + 1;
                if (!vis[next]) { vis[next] = true; q.offer(new int[]{next, cur[1] + 1}); }
            }
        }
        return 0;
    }
}
Approach 3

Level III: Optimal Greedy (Window-Based BFS)

Intuition

Maintain a 'window' of reachable indices for the current number of jumps. When we reach the end of the current window, we increment jump count and move to the farthest point reachable from that window.

Thought Process

  1. jumps, curEnd, farthest variables.
  2. Iterate through array (excluding last index).
  3. Update farthest = max(farthest, i + nums[i]).
  4. If i == curEnd, update curEnd = farthest, jumps++.

Pattern: Greedy Reachability

⏱ O(N)💾 O(1)

Detailed Dry Run

[2,3,1,1,4] i=0: f=2. i==curEnd(0). end=2, jumps=1. i=1: f=4. OK. i=2: f=4. i==curEnd(2). end=4, jumps=2. Result: 2.
java
public class Solution {
    public int jump(int[] nums) {
        int jumps = 0, curEnd = 0, farthest = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            farthest = Math.max(farthest, i + nums[i]);
            if (i == curEnd) {
                jumps++;
                curEnd = farthest;
            }
        }
        return jumps;
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionMinimum Cost to Merge Stones
Next Question →Gas Station