Jump Game II

Master this topic with zero to advance depth.

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

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

Pattern: DAG Shortest Path

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

Detailed Dry Run

nums = [2, 3, 1, 1, 4]

i	Range	Best Next	dp[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-1$ is reached.

Thought Process

Queue stores (index, levels).
Use visited set to avoid cycles/redundancy.
For each popped index, push all unvisited neighbors $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

jumps, curEnd, farthest variables.
Iterate through array (excluding last index).
Update farthest = max(farthest, i + nums[i]).
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;
    }
}

← Previous QuestionMinimum Cost to Merge Stones

Next Question →Gas Station

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.