LeetCode 45 Jump Game II: Master the Greedy Solution Interviewers Grill You On
This comprehensive guide deconstructs LeetCode 45 Jump Game II, walking through brute force, DP, BFS, and optimal greedy solutions with correctness proofs, Java implementations, complexity benchmarks, eight common pitfalls, comparison with Jump Game I, and eight high-frequency interview follow-up questions.
Problem Overview
LeetCode 45 "Jump Game II" asks: given a non-negative integer array nums where nums[i] is the maximum jump length from index i, start at index 0 and return the minimum number of jumps to reach the last index n-1. The problem guarantees reachability. Example: nums = [2,3,1,1,4] → optimal path 0 → 1 → 4 in 2 jumps.
Before coding, align three key points: (1) nums[i] is the maximum jump, not mandatory; (2) reachability is guaranteed; (3) we seek minimum jump count , not path or mere reachability (that's LeetCode 55).
Solution Evolution: From Brute Force to Optimal Greedy
Stage 1: Brute Force Backtracking – Try all step counts at each position, recursive search. Complexity: O(2ⁿ) exponential. Interview rating: ❌ Only shows you read the problem.
Stage 2: Dynamic Programming – dp[i] = min jumps to reach i, relax entire reachable interval. Complexity: O(n²) / O(n). Interview rating: ⭐ Passes but not impressive.
Stage 3: BFS Layer-by-Layer – Each jump = one layer; layer number = step count. Complexity: O(n) / O(n). Interview rating: ✅ Very intuitive.
Stage 4: Greedy Compression – No queue, maintain only two boundaries. Complexity: O(n) / O(1) . Interview rating: 🏆 Optimal, heavily tested.
DP Stepping Stone
Define dp[i] as minimum jumps to reach index i. For each i, relax the entire interval it can reach:
public int jumpDp(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = 0; i < n; i++) {
if (dp[i] == Integer.MAX_VALUE) continue;
for (int j = i + 1; j <= Math.min(n - 1, i + nums[i]); j++) {
dp[j] = Math.min(dp[j], dp[i] + 1);
}
}
return dp[n - 1];
}O(n²) time, O(n) space. The same interval gets relaxed repeatedly — that's the waste. Interviewer will ask: "Can you do better?"
Key Insight: Treat Each Jump as a BFS Layer
Every jump has uniform cost = 1. So make each jump go as far as possible — that's greedy. Reframe: jump 1 covers [0,0], jump 2 starts from all positions jump 1 could reach… each jump is a BFS layer, and the first layer touching the end gives the minimum steps . Each layer's coverage is a continuous index segment — no real queue needed, just two variables: curEnd: Right boundary of current jump's coverage. Intuition: "Red line" of this jump; keep scouting until you hit it. farthest: Farthest index next jump can reach from current layer. Intuition: Scout's farthest discovery. steps: Jump count so far. Intuition: Number of key decisions made.
When scanning pointer i hits curEnd, the current layer is exhausted — must jump : steps++, curEnd = farthest.
One-sentence greedy essence: Don't obsess over where each jump lands; just record the farthest reachable point within the current jump's range. When you hit the boundary, jump decisively. Like Super Mario — you only care: how far can this jump reach, and while getting there, scout the next jump's range.
Step-by-Step Execution Trace: [2,3,1,1,4]
Index: 0 1 2 3 4
nums: [ 2, 3, 1, 1, 4 ] 🎁
Init: curEnd=0 farthest=0
🚀 Jump 1 (i = 0):
farthest = max(0, 0+2) = 2
i == curEnd(0) → jump! steps=1, curEnd=2
🚀 Jump 2 (i = 1, 2):
i=1: farthest = max(2, 1+3) = 4 ← scout finds treasure
i=2: farthest = max(4, 2+1) = 4
i == curEnd(2) → jump! steps=2, curEnd=4
curEnd(4) >= n-1(4) → reached end, early exit 🎉
Answer = 2 (path 0 → 1 → 4)Variable flow:
i=0, nums[i]=2, farthest=2, i==curEnd? Yes, steps=1, curEnd=2
i=1, nums[i]=3, farthest=4, i==curEnd? No, steps=1, curEnd=2
i=2, nums[i]=1, farthest=4, i==curEnd? Yes, steps=2, curEnd=4 (≥ n-1, done)
Core Code (Java Interview Standard)
class Solution {
public int jump(int[] nums) {
int n = nums.length;
if (n <= 1) return 0; // start == end, 0 steps
int steps = 0; // jumps taken
int curEnd = 0; // current jump's right boundary
int farthest = 0; // next jump's farthest reach
// ⚡ Note: i < n - 1, don't process last element
for (int i = 0; i < n - 1; i++) {
// ① Continuous scouting: within current range, how far can next jump reach?
farthest = Math.max(farthest, i + nums[i]);
// ② Hit current jump's boundary → must jump
if (i == curEnd) {
steps++;
curEnd = farthest;
// ③ Pruning: already can reach end, stop early
if (curEnd >= n - 1) break;
}
}
return steps;
}
}Complexity: ⏱️ O(n) single pass | 💾 O(1) three variables.
Layered BFS Version (Better for Explaining & Proving)
class Solution {
public int jump(int[] nums) {
int n = nums.length, jumps = 0, start = 0, end = 0;
while (end < n - 1) { // haven't covered end yet, expand another layer
int farthest = 0;
for (int i = start; i <= end; i++) // only scan current layer
farthest = Math.max(farthest, i + nums[i]);
start = end + 1; // next layer's left boundary
end = farthest; // next layer's right boundary
jumps++; // expand one layer = one jump
}
return jumps;
}
}⚠️ Must say this out loud: Looks like nested loops, but inner index moves monotonically forward, each index visited exactly once , total visits = n , amortized O(n). Without this, interviewer thinks you wrote O(n²). Also explains why no real queue needed — each layer is a continuous segment, two pointers express the whole layer, equivalent BFS with smaller constant.
Four Technical Highlights in the Code (Proactively Mention in Interview!)
<strong>i == curEnd</strong>is the "implicit BFS layer switch" . Standard BFS uses queue.size() to control a layer; here "index equals boundary" replaces it, compressing space from O(n) to O(1) — squeezing BFS queue into two variables, that's the art of greedy.
Loop to n - 1 : the end doesn't need another "jump". Writing i < n often works by accident (saved by n=1 guard and boundary coincidence) — code relying on luck gets spotted instantly . Say: "I'm already at the finish line, no need to take another step."
steps++ bound to "boundary event" : not blindly incrementing in loop, but "record only when layer finishes", naturally matching BFS layer counting.
Early break : curEnd >= n - 1 means remaining indices add no value. E.g., nums = [5,1,1,1,1] reaches end in one jump; early stop saves time and is logically correct termination.
Use semantic variable names ( curEnd / farthest not a / b) — readability is productivity.
Why Is Greedy Correct? (Interviewer Will Almost Certainly Ask)
Saying "feels like jumping farthest works" gets you flagged as memorizing. Three solid explanations, pick any:
Explanation 1: BFS Perspective (Easiest to Grasp)
One jump = one BFS layer. Layer k covers interval [L_k, R_k] where R_k = max(i + nums[i]) for i ∈ [L_{k-1}, R_{k-1}]. No matter which specific point in the interval you land on, the next layer's boundary is identical — so "where exactly you jump" doesn't matter, only how far the boundary extends. BFS layer number by definition equals shortest path length; greedy is strictly equivalent to BFS, hence optimal.
Explanation 2: Exchange Argument
Let an optimal solution's first jump land at p, greedy picks q. Greedy rule guarantees from q the farthest reachable point is ≥ that from p. Swap optimal's first jump to q — remaining path still works, step count unchanged — greedy is no worse than optimal, and since it's feasible, it is optimal.
Explanation 3: Induction
Assume k -th jump reaches farthest end_k. The k+1 -th optimal jump must start from [0, end_k], and our maintained farthest during scan is exactly the optimal end_{k+1}. Each step takes the optimal value, so total steps are minimal.
🎁 Bonus point sentence: Greedy works here because every jump cost is exactly 1 . If costs differ (e.g., varying stamina), greedy fails immediately — must fall back to DP or Dijkstra shortest path. Proactively stating the algorithm's applicability condition is a strong plus.
Complexity Comparison & Benchmark Data
Greedy (Forward Scan) : Time O(n) , Space O(1) — Primary choice, write this directly.
Greedy (Layered BFS) : Time O(n) (amortized), Space O(1) — For explaining approach & proving correctness.
Real Queue BFS : Time O(n), Space O(n) — Understand essence, larger constant.
Dynamic Programming : Time O(n²), Space O(n) — Stepping stone to greedy.
Reverse Greedy : Time O(n²), Space O(1) — Only for verbal description, don't code.
Brute Force Backtracking : Time O(2ⁿ), Space O(n) — One-liner mention.
Local Benchmark (JDK 17):
Scenario: n = 10⁴, nums[i] = 1000 → Greedy: 0.41 ms, DP: 12.25 ms
Scenario: n = 10⁷, nums[i] = 1000 → Greedy: 10.2 ms, DP: — (too slow)
Same n, ~30x gap ; next order of magnitude, DP crashes. So when asked "Can you handle 10⁵?", O(n) single pass is trivial.
Eight Pitfalls (I Stepped On Them So You Don't Have To)
Loop end: n vs n-1 – Writing i < n triggers i == curEnd at last index, overcounts one jump. Fix: i < n - 1: last index reached = done, no jump needed from it.
Boundary trigger timing – Early steps++ overcounts; late misses entire layer. Rule: only jump after all positions in current layer are scanned .
n = 1 degenerate input – Loop yields wrong answer. Guard: if (n <= 1) return 0; (loop condition naturally handles it, but explicit is safer).
nums[i] = 0 "zombie" cells – Fear of getting stuck. Harmless here — boundary advances by farthest, not nums[i]; but in LC 55 must return false when i > maxReach.
Wrong initial boundary – curEnd = nums[0]. Correct: curEnd = 0, 0th jump position is 0.
Integer overflow – i + nums[i] theoretical overflow. Write Math.min(n - 1, i + nums[i]), also speeds comparison.
Layered version misjudged as O(n²) – Outer while + inner for looks like double loop. Explicitly state inner index moves monotonically, total visits = n.
Blindly applying greedy to variants – Wrong answer when costs differ. Proactively declare: unequal cost → back to DP/Dijkstra; negative numbers → greedy also fails.
Difference from LeetCode 55 (Must-Know)
Question : LC 55 asks Can reach end? LC 45 asks Minimum jumps to end?
Core : LC 55 maintains maxReach, checks i > maxReach. LC 45 maintains curEnd + farthest, layer counting.
Termination : LC 55 early return false. LC 45 guaranteed reachable, return step count.
Essence : LC 55 is reachability problem. LC 45 is optimality problem.
Proactively comparing these two shows systematic preparation. Related family to pack together:
LC 55: Jump Game I – Only reachability.
LC 1306: Jump Game III – Can jump forward/backward, BFS/DFS graph search.
LC 1345: Jump Game IV – Same value = teleport, BFS + hash grouping.
LC 1871: Jump Game VII – Sliding window + reachability.
LC 403: Frog Jump – DP + hash acceleration.
Eight High-Frequency Interview Follow-Ups (Pre-Positioned)
Q1: What if reachability isn't guaranteed? At i == curEnd, check if farthest > curEnd. If farthest == curEnd and i != n-1, interval can't expand → return -1. Tests "no-solution branch" awareness (fusion of 45 + 55).
Q2: Output the actual jump path? Record a source index per layer (BFS parent, captured while probing farthest), then backtrack from end. Space goes from O(1) to O(jump count).
Q3: Why not use a real queue for BFS? Each jump covers a continuous index segment; two pointers express the whole layer, saving enqueue/dequeue and O(n) extra space. Equivalent BFS, smaller constant.
Q4: Can it be faster? No lower than O(n). Every element must be examined at least once, otherwise nums[i] 's info isn't fully used. O(n) is the lower bound.
Q5: Array all 1s? Answer = n - 1, each jump moves one step — greedy's degenerate case, code works without special handling.
Q6: Change to "total number of paths to end"? Greedy fails, reverts to DP: dp[i] = Σ dp[j] (all j that can reach i), O(n²). Problem shifts from "find optimum" to "count".
Q7: Huge array, streaming input? Still O(1) state, update farthest and curEnd on the fly — naturally supports stream processing , an engineering advantage of greedy over DP.
Q8: Reverse greedy version? Exists — scan right-to-left maintaining "leftmost position that can reach current target", also O(n), but forward is more intuitive and easier to explain.
Interview Battle Kit
Recommended Opener (Memorize):
"Okay. Let me restate: goal is minimum jumps, not reachability. Since reachability is guaranteed, my first thought is greedy — O(n) time, O(1) space. I'll walk through brute force first, then show how to optimize to greedy. Sound good?"
This opener lays out complexity upfront and sets rhythm.
Closing Script (After Code):
"Summary: core idea is using 'interval boundaries' instead of 'per-point decisions' — delayed decision + boundary trigger. Don't decide where to jump immediately; walk until you must jump, then decide based on the farthest boundary scouted so far. Time O(n), space O(1). Correctness via BFS layering or exchange argument."
If you can draw curEnd / farthest alternating updates on whiteboard while explaining, and write n-1 and break optimizations correctly, this is Strong Hire level.
One-Minute Cheat Sheet:
One-sentence model: One jump = BFS layer; curEnd = current layer right boundary, farthest = next layer right boundary.
Two actions: scan & update farthest; when i hits curEnd → steps++ and push boundary to farthest.
Three details: n <= 1 return 0; loop to n-1; early break when end reached.
Complexity: O(n) / O(1).
Bonus line: Jump cost ≡ 1 enables greedy; unequal cost → must use DP.
Self-Check Checklist:
[ ] Can verbally trace [2,3,1,1,4] scan without looking at code.
[ ] Can explain why loop is i < n - 1 not i < n.
[ ] Can prove greedy correctness via BFS layering or exchange argument.
[ ] Can explain why layered version is amortized O(n).
[ ] Know how nums[i] = 0 differs between LC 45 and LC 55.
[ ] Can proactively state "greedy fails when jump costs differ".
[ ] Whiteboard code passes first try, no boundary bugs.
Final Thought
The essence isn't "jump farthest each step" but within current visibility, find the point that maximizes next step's visibility — the key to fewer detours is seeing farther, not running faster. One actionable tip: don't just AC and move on. Run through the checklist above — proofs, follow-ups, edge cases — only then do you truly own this problem (code tested on JDK 17, 6 samples pass, cross-verified against DP on 130k+ random cases).
Signed-in readers can open the original source through BestHub's protected redirect.
This article has been distilled and summarized from source material, then republished for learning and reference. If you believe it infringes your rights, please contactand we will review it promptly.
How this landed with the community
Was this worth your time?
0 Comments
Thoughtful readers leave field notes, pushback, and hard-won operational detail here.
