Greedy — Jump Game II
↗ LeetCode: Jump Game II · Medium · pattern chapter →
Given nums[i] = max jump length from index i, return the minimum jumps to reach the last index. Guaranteed reachable.
Example 1 — [2,3,1,1,4] → 2 (0 → 1 → 4) Example 2 — [2,3,0,1,4] → 2
Constraints — 1 ≤ n ≤ 10⁴; 0 ≤ nums[i] ≤ 1000. Brute DP with min-jumps[i] is O(n²) = 10⁸ ops at n=10⁴ (borderline). Greedy expanding-frontier ("BFS levels on an implicit graph") is O(n) = 10⁴ ops.
Interview timer00:00
Approach 1 — BFS (level = jump count)
Intuition. Model the problem as BFS: each index is a node with edges to [i+1, i+nums[i]]. Level of last index = min jumps.
int jumpBFS(int[] a) {
int n = a.length;
if (n <= 1) return 0;
boolean[] seen = new boolean[n];
Deque<Integer> q = new ArrayDeque<>();
q.offer(0); seen[0] = true;
int level = 0;
while (!q.isEmpty()) {
level++;
for (int i = q.size(); i > 0; i--) {
int u = q.poll();
for (int v = u + 1; v <= Math.min(u + a[u], n - 1); v++) {
if (v == n - 1) return level;
if (!seen[v]) { seen[v] = true; q.offer(v); }
}
}
}
return -1;
}Complexity — Time O(n²) worst-case; Space O(n).
Approach 2 — DP (min jumps from each index)
Intuition. dp[i] = min jumps to reach n-1 from i. dp[n-1] = 0; dp[i] = 1 + min(dp[i+1..i+a[i]]). Fill right to left.
int jumpDP(int[] a) {
int n = a.length;
int[] dp = new int[n];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[n - 1] = 0;
for (int i = n - 2; i >= 0; i--)
for (int j = i + 1; j <= Math.min(i + a[i], n - 1); j++)
if (dp[j] != Integer.MAX_VALUE) dp[i] = Math.min(dp[i], dp[j] + 1);
return dp[0];
}Complexity — Time O(n²); Space O(n).
Approach 3 — Greedy (frontier expansion)
Insight from DP. Because all edges have weight 1, BFS's "levels" have a very simple shape — we just need to know how far each level reaches. Track farthest (best reach considering all indices in the current level). When we hit end (level boundary), commit a jump and set end = farthest.
Trap. Commit jumps++ when i == end, not on every scan step.
int jump(int[] a) {
int end = 0, farthest = 0, jumps = 0;
for (int i = 0; i < a.length - 1; i++) {
farthest = Math.max(farthest, i + a[i]);
if (i == end) { jumps++; end = farthest; }
}
return jumps;
}Complexity — Time O(n); Space O(1). Optimal.
Try it yourself
Complexity summary
| Approach | Time | Space |
|---|---|---|
| BFS | O(n²) | O(n) |
| DP right-to-left | O(n²) | O(n) |
| Greedy frontier | O(n) | O(1) |
When to use which
- Cold interview → walk BFS → greedy. Show the "levels shape enables O(1)" insight.
- Interviewer wants a proof → BFS gives you the shortest-path guarantee; greedy is a tighter special case.
Related problems (same ladder applies)
- Jump Game I — reachability instead of min jumps
- Jump Game III — BFS with two edges per node
- Video Stitching — same greedy frontier expansion
- Minimum Number of Taps to Open — reframe intervals → same greedy