Loading…

mediumGreedyLC #45Frequently asked

Jump Game II

Q: How do you solve Jump Game II using the Dynamic Programming — Min Jumps to Each Index approach?

When to use it: Lead with this to show you can model min-jumps formally as a recurrence, then flag the O(n²) range scan as the cost to eliminate. Define `dp[i]` = the minimum number of jumps needed to arrive at index `i`, with `dp[0] = 0`. Process indices left to right; from a reachable `i`, every index `j` in `[i+1, i+nums[i]]` can be reached in `dp[i] + 1` jumps, so we relax `dp[j] = min(dp[j], dp[i] + 1)`. The answer is `dp[n−1]`. **Why left to right works.** To reach `j`, you must have first reached some earlier `i` whose jump range covers `j`. Filling left to right guarantees that when we *use* `dp[i]` to relax forward, `dp[i]` is already final — its value was settled by even earlier indices. So each forward relaxation reads a correct minimum. **Why we relax the whole reachable range.** A single index `i` doesn't pick one target; it can reach an entire contiguous block `[i+1, i+nums[i]]`, all in one extra jump. To find the minimum jumps to every index, we must offer `dp[i] + 1` to *each* index in that block and keep the smallest offer any predecessor makes. That's the `min` relaxation over a range. **Why we don't ship this.** That per-index range relaxation is the quadratic cost: with `n = 10⁴` and large jump values, you can approach 10⁸ relaxations. The DP is the honest way to *define* min-jumps and prove the recurrence, but it recomputes information that the contiguous-window structure makes free. The greedy notices that the indices sharing the same `dp` value form a contiguous band — a BFS level — and processes each band in O(1) amortised. **Why the DP still earns its keep.** Stating it shows the interviewer you can formalise shortest-jumps as a relaxation, and it makes the leap to BFS levels obvious: the set `{i : dp[i] = k}` is exactly the k-th BFS layer, and those layers are contiguous because every reach is an interval. Time complexity: O(n²). Space complexity: O(n).

LCPractice

Greedy Algorithms · 2 of 23 · 10 min

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].

In plain English

Starting at index 0, each cell gives the maximum forward hop length. Find the fewest hops needed to land on (or past) the final index. Reachability is guaranteed, so the answer always exists — you only need the minimum count, not the route.

Examples

Example 1

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

Example 2

Input: nums = [2, 3, 0, 1, 4]
Output: 2
Note: Index 0 → index 1 (reach covers up to index 4), then index 1 → index 4. Two jumps.

Example 3

Input: nums = [0]
Output: 0
Note: Already on the last index — zero jumps.

Constraints

1 ≤ nums.length ≤ 10⁴
0 ≤ nums[i] ≤ 1000
It is guaranteed you can reach the last index
From index i you may jump to any index in [i+1, i+nums[i]]

Clarifying questions4First question: Must I jump exactly nums[i], or up to nums[i]?Explore questions

Q1.Must I jump exactly nums[i], or up to nums[i]?
Up to — any length from 1 to nums[i]. That 'up to' makes the set of indices reachable in k jumps a contiguous window, which the greedy exploits.
Q2.Is reaching the last index always possible?
Yes, the problem guarantees it. So unlike Jump Game I, I never return -1 or handle a stuck state.
Q3.If the array has one element, what's the answer?
0 — you're already on the last index, no jumps needed. The loop-to-n−1 bound handles this naturally.
Q4.Can I overshoot the last index?
Yes, a jump that lands at or beyond n−1 counts as reaching it. We clamp ranges to n−1 in the DP and stop the greedy loop early.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Each value is the max jump length from that index; return the minimum number of jumps to reach the last index (reachability is guaranteed). The DP fills minimum jumps per index in O(n²). The optimal greedy treats it as a BFS over levels: the indices reachable in exactly k jumps form a contiguous window, so track the current window's end and the farthest index the whole window can reach; every time the cursor hits the window end you've spent one jump and the window expands. O(n) time, O(1) space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognise this as a shortest-path/BFS problem and then realise the contiguous reachability lets you collapse the BFS queue into two scalars — plus whether you handle the off-by-one (loop to n−1) that prevents an extra jump.

Where candidates slip

Counting a jump at every index instead of only when the cursor reaches the current window's end, or looping to n and double-counting a jump when the last index coincides with curEnd.

How to stand out

Name it as BFS over levels, present the O(n²) DP to show you can model min-jumps formally, then collapse to the O(n) two-pointer-of-windows greedy and justify why scanning a window and tracking its farthest reach is exactly a BFS layer.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Dynamic Programming — Min Jumps to Each Index	`O(n²)`	`O(n)`	Lead with this to show you can model min-jumps formally as a recurrence, then flag the O(n²) range scan as the cost to eliminate.	Read
2	Greedy — BFS Over Contiguous Levels (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Frame it as 'BFS where each level is a contiguous window, so I replace the queue with curEnd and farthest' and justify why a window scan equals a BFS layer.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewMinimum jumps to reach the last indexHow to count min jumps?Model per indexShortest pathExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Dynamic Programming — Min Jumps to Each Index

TimeO(n²)SpaceO(n)

Lead with this to show you can model min-jumps formally as a recurrence, then flag the O(n²) range scan as the cost to eliminate.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Let dp[i] be the minimum jumps to reach index i. dp[0] = 0. How does reaching i depend on earlier indices?

2Hint 2Explore hint

From index i you can extend to any j in [i+1, i+nums[i]] with one more jump, so dp[j] = min(dp[j], dp[i] + 1).

3Hint 3Explore hint

Sweep left to right, relaxing each index's reachable range. The answer is dp[n−1].

A · Core idea

Define dp[i] = the minimum number of jumps needed to arrive at index i, with dp[0] = 0. Process indices left to right; from a reachable i, every index j in [i+1, i+nums[i]] can be reached in dp[i] + 1 jumps, so we relax dp[j] = min(dp[j], dp[i] + 1). The answer is dp[n−1].

Why left to right works. To reach j, you must have first reached some earlier i whose jump range covers j. Filling left to right guarantees that when we use dp[i] to relax forward, dp[i] is already final — its value was settled by even earlier indices. So each forward relaxation reads a correct minimum.

Why we relax the whole reachable range. A single index i doesn't pick one target; it can reach an entire contiguous block [i+1, i+nums[i]], all in one extra jump. To find the minimum jumps to every index, we must offer dp[i] + 1 to each index in that block and keep the smallest offer any predecessor makes. That's the min relaxation over a range.

Why we don't ship this. That per-index range relaxation is the quadratic cost: with n = 10⁴ and large jump values, you can approach 10⁸ relaxations. The DP is the honest way to define min-jumps and prove the recurrence, but it recomputes information that the contiguous-window structure makes free. The greedy notices that the indices sharing the same dp value form a contiguous band — a BFS level — and processes each band in O(1) amortised.

Why the DP still earns its keep. Stating it shows the interviewer you can formalise shortest-jumps as a relaxation, and it makes the leap to BFS levels obvious: the set {i : dp[i] = k} is exactly the k-th BFS layer, and those layers are contiguous because every reach is an interval.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

i=0 (dp=0)

reach [1,2]; dp[1]=1, dp[2]=1

Statedp = [0,1,1,∞,∞]

Final result2

C · Code with teaching comments

Reference implementation previewpublic int jump(int[] nums) { int n = nums.length; int[] dp = new int[n]; Arrays.fill(dp, Integer.MAX_VALUE); dp[0] = 0;Explore the full code

solution.javaJava

Dynamic Programming — Min Jumps to Each Index — reference

5 teaching notes

1
public int jump(int[] nums) {
2
    int n = nums.length;
3
    int[] dp = new int[n];
4
    // Unreached indices start at infinity; only relaxations bring them down.
5
    Arrays.fill(dp, Integer.MAX_VALUE);
6
    // We begin on index 0 with zero jumps spent — the base case.
7
    dp[0] = 0;
8
    for (int i = 0; i < n; i++) {
9
        if (dp[i] == Integer.MAX_VALUE) continue;
10
        // Clamp the reachable range to the array's last index.
11
        int far = Math.min(i + nums[i], n - 1);
12
        for (int j = i + 1; j <= far; j++) {
13
            // Reaching j via i costs one more jump than reaching i — keep the smallest
14
            // such cost.
15
            dp[j] = Math.min(dp[j], dp[i] + 1);
16
        }
17
    }
18
    // Minimum jumps to the last index — the whole question.
19
    return dp[n - 1];
20
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.20 lines

D · Why it works and complexityO(n²) timeO(n) spaceOpen the invariant and proofExplore the proof

The DP reveals the fact the greedy exploits: indices with the same minimum jump count form a contiguous window, because each index reaches an interval and intervals union into intervals. Once you see that 'dp[i] = k' carves the array into consecutive bands, you realise you don't need n separate dp cells — just the boundary of the current band.

ComplexityO(n²) time, O(n) space — For each of n indices we relax up to its full jump range (length up to nums[i]), so the worst case is O(n²) time; the dp array uses O(n) space.

E · Edge cases and pitfalls5nums = [0] — n=1, dp[0]=0, loop relaxes nothing (range empty), returns dp[0]=0.Explore edge cases

Edge cases handled

nums = [0]n=1, dp[0]=0, loop relaxes nothing (range empty), returns dp[0]=0.
nums = [1, 1, 1, 1]Each index reaches only the next, so dp = [0,1,2,3]; returns 3.

Pitfalls

Forgetting to clamp i + nums[i] to n−1 — out-of-bounds writes on large jump values.
Relaxing from an index whose dp is still infinity — propagates garbage (guard with the continue).
Shipping O(n²) when n = 10⁴ makes the linear greedy clearly preferable.

03.2

Approach 2 of 2 · Optimal

Greedy — BFS Over Contiguous Levels (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Frame it as 'BFS where each level is a contiguous window, so I replace the queue with curEnd and farthest' and justify why a window scan equals a BFS layer.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Think BFS: level 0 is index 0, level 1 is everything reachable in one jump, level 2 in two jumps, and so on. The answer is the level number of the last index.

2Hint 2Explore hint

Because each index reaches a contiguous range, each level is itself a contiguous window. Track curEnd = the right edge of the current level and farthest = the furthest the whole current level can reach.

3Hint 3Explore hint

Scan left to right updating farthest. When the cursor i hits curEnd, you've consumed the entire current level → increment jumps and set curEnd = farthest. Loop only to n−1 to avoid an extra phantom jump.

A · Core idea

Run BFS without a queue. Maintain curEnd = the right boundary of the current BFS level (the farthest index reachable in jumps jumps) and farthest = the farthest index reachable in jumps + 1 jumps, discovered by scanning the current level. Sweep i from 0 to n−2, updating farthest = max(farthest, i + nums[i]). When i reaches curEnd, the current level is fully explored, so increment jumps and advance curEnd = farthest to the next level's boundary.

Why this is literally BFS. Model each index as a node with edges to every index in its jump range. BFS explores nodes in waves: all nodes at distance k before any at distance k+1, and the first time it reaches the target gives the shortest distance. The set of indices at BFS distance k is exactly {i : min jumps to i = k}. The crucial structural fact: because a jump goes up to nums[i], the indices reachable in k jumps form a contiguous window [prevEnd+1, curEnd] — there are no gaps. So instead of a queue holding individual nodes, the entire level is described by one number, curEnd, and we discover the next level's extent with a running farthest.

Why a jump is counted only at `i == curEnd`. While i is still inside the current window (i < curEnd), we're examining nodes that all sit at the same BFS distance — we haven't spent another jump yet, we're just gathering how far this level collectively reaches. The instant i equals curEnd, we've examined every node of the current level; to go further we must take one more jump, so we increment jumps and roll the window forward to farthest. Counting a jump per index instead would massively over-count; counting it at the window edge counts exactly one jump per BFS layer.

Why the greedy is optimal — the exchange/contradiction argument. BFS is provably shortest for unweighted graphs, but here's the direct exchange argument for why scanning a window and taking its maximum reach can't be beaten. Within the current level [lo, curEnd], suppose the optimal solution jumps to some index p in this window and from there reaches index q. Our greedy doesn't commit to a single p; it records farthest = max over all i in the window of (i + nums[i]), which is >= q for every choice p the optimal could make. Now suppose, for contradiction, that the greedy used more jumps than optimal to reach the end. Consider the first level where they diverge: optimal reaches some index x using k jumps. Greedy's curEnd after k jumps is the maximum index reachable in k jumps, so curEnd >= x — greedy is at least as far along after the same number of jumps. By induction this holds at every level, so greedy reaches (or passes) the last index in no more jumps than optimal. The maximum-reach window dominates any specific sequence of choices, which is exactly why the greedy never needs to backtrack or pick a particular landing index.

Why loop to `n − 1`, not `n`. If the last index coincides with a curEnd, iterating onto it would trigger one final jumps++ for a jump we never actually take (we're already there). Stopping at n − 2 guarantees we count a jump only for transitions that genuinely advance us, so nums = [0] correctly yields 0.

Why this beats the DP. The DP recomputes dp[j] for every j in every range; the greedy notices those values form contiguous levels and tracks only the level boundary plus a running max, collapsing O(n²) to O(n) and O(n) space to O(1).

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Interactive diagram

BFS levels as contiguous windows

i=0

Active call / nodeSupporting contextReturned stateNot active

Each jump count is a BFS layer; 'jump up to k' makes every layer a gap-free interval, so two integers replace the queue.

Final result2

C · Code with teaching comments

solution.javaJava

Greedy — BFS Over Contiguous Levels (Optimal) — optimal

5 teaching notes

1
public int jump(int[] nums) {
2
    // jumps = BFS depth so far, curEnd = current level's right edge, farthest = next
3
    // level's reach.
4
    int jumps = 0, curEnd = 0, farthest = 0;
5
    // Stop at n−2 so landing on the last index doesn't trigger a phantom extra jump.
6
    for (int i = 0; i < nums.length - 1; i++) {
7
        // Extend how far the CURRENT level can reach — the next level's boundary.
8
        farthest = Math.max(farthest, i + nums[i]);
9
        // Cursor reached the end of this level → all of it explored, one more jump is
10
        // required to continue.
11
        if (i == curEnd) {
12
            jumps++;
13
            curEnd = farthest;
14
        }
15
    }
16
    return jumps;
17
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.17 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

The unlock is seeing 'minimum jumps' as 'BFS depth', then noticing that 'jump up to k' makes every BFS layer a gap-free interval — so the queue degenerates into two integers. You don't choose which index to jump to inside a layer; you only track how far the whole layer can throw you, and that maximum dominates every individual choice. This window-as-level idea is the seed for many 'minimum moves on a line' problems.

ComplexityO(n) time, O(1) space — A single left-to-right pass with O(1) work per index (one max, one comparison) gives O(n) time, and we keep just three integers — jumps, curEnd, farthest — so O(1) space.

E · Edge cases and pitfalls6nums = [0] — Loop runs for i in range(0) — never executes — so jumps stays 0. Already on the last index.Explore edge cases

Edge cases handled

nums = [0]Loop runs for i in range(0) — never executes — so jumps stays 0. Already on the last index.
nums = [2, 1]i=0: farthest=2, i==curEnd → jumps=1, curEnd=2; loop ends (n−1=1). Returns 1.
nums = [1, 2, 1, 1, 1]Levels: [0]→[1]→[2,3]→[4]; cursor hits each curEnd, yielding 3 jumps.

Pitfalls

Looping to n instead of n−1 — double-counts a jump when the last index equals curEnd.
Incrementing jumps at every index rather than only when i reaches curEnd.
Overwriting farthest = i + nums[i] without the max — a small later jump shouldn't shrink the next level's reach.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic 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) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Counting a jump per index

All indices inside the current window sit at the same BFS depth. Incrementing jumps for each of them counts steps you never took — the count balloons far above the true minimum.

Explore the code comparison

Don't write this

jumps = 0
for i in range(len(nums) - 1):
    farthest = max(farthest, i + nums[i])
    jumps += 1            # wrong: counts every index

Write this instead

jumps = 0
for i in range(len(nums) - 1):
    farthest = max(farthest, i + nums[i])
    if i == cur_end:      # only at the window boundary
        jumps += 1
        cur_end = farthest

Looping to n instead of n−1

If the last index equals curEnd, iterating onto it fires one more jumps++ for a jump that never happens — you're already standing on the goal.

Explore the code comparison

Don't write this

for (int i = 0; i < nums.length; i++) { // includes last index
    farthest = Math.max(farthest, i + nums[i]);
    if (i == curEnd) { jumps++; curEnd = farthest; }
}

Write this instead

for (int i = 0; i < nums.length - 1; i++) {
    farthest = Math.max(farthest, i + nums[i]);
    if (i == curEnd) { jumps++; curEnd = farthest; }
}

Letting a small jump shrink the next level

Assigning farthest = i + nums[i] without the max can pull the next level's boundary backward when a later index has a tiny value, undercounting reach and inflating jumps.

Explore the code comparison

Don't write this

farthest = i + nums[i]; // overwrites a bigger earlier reach

Write this instead

farthest = Math.max(farthest, i + nums[i]);

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Greedy BFS levels — current window end + farthest reach

Code pattern to memorize

jumps = 0; curEnd = 0; farthest = 0
for i in range(n - 1):          # stop before the last index
    farthest = max(farthest, i + nums[i])
    if i == curEnd:             # finished this jump's reachable window
        jumps += 1
        curEnd = farthest        # window expands to the next level
return jumps

Rules to remember

1Think in levels: indices reachable in exactly k jumps are a contiguous window — BFS over the array, no explicit queue.
2Carry `farthest` = the furthest index the current window can reach, updated at every index you pass.
3Carry `curEnd` = the right edge of the current level; when i == curEnd you've exhausted this jump's reach, so `jumps++` and set curEnd = farthest.
4Loop only to `n − 1`, never n — landing on the last index shouldn't trigger one extra phantom jump.
5You never need to know which index you jumped to inside a window — only how far the whole window reaches, which is why greedy = BFS here.
6The problem guarantees reachability, so you don't handle the stuck case (that's Jump Game I).

Use this pattern when

Minimum steps / shortest path on a line where each position grants a forward range
Reachable-in-k-moves sets form contiguous windows (jump *up to* k)
You want BFS's shortest-path guarantee without building a graph
Only the count of jumps matters, not the exact path

Choose another pattern when

Edge weights vary (cost per jump differs) → Dijkstra, not uniform BFS levels
Jumps can go backward or to arbitrary targets → real graph BFS with a queue
You must return the actual jump sequence → augment with parent pointers
Only feasibility (yes/no), not the count → Jump Game I's single-frontier greedy

Interview takeaway

Jump Game II is BFS in disguise: because 'jump up to k' makes each level a contiguous window, you replace the queue with two integers — the window's end and its farthest reach — and count a jump each time the window flips over. The same level-window trick reduces many 'minimum moves on a line' problems from O(n²) to O(n).

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternCanonical 'BFS over contiguous levels' greedy: minimum moves on a line where each position reaches an interval, so each BFS layer is a gap-free window and the queue collapses into curEnd + farthest. Recognise it for min-jumps / min-taps / interval-covering problems; it's the counting sibling of Jump Game's feasibility frontier.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Jump Game
Feasibility only (can you reach the end?) — single farthest frontier, no jump counting.
Jump Game III
Coming soon
Jumps go i±nums[i] to a zero — true graph BFS/DFS, levels are no longer contiguous.
Jump Game IV
Coming soon
Jump ±1 or to equal-valued indices — explicit BFS with a queue and value-buckets.
Minimum Number of Taps to Open to Water a Garden
Coming soon
Same min-jumps-as-BFS-windows greedy, reframed as covering an interval with ranges.

Same pattern

←

Jump Game

Continue · Next problem

Gas Station

mediumGreedyLC #45Frequently asked

Jump Game II

LCPractice

Greedy Algorithms · 2 of 23 · 10 min

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

In plain English

Examples

Example 1

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

Example 2

Input: nums = [2, 3, 0, 1, 4]
Output: 2
Note: Index 0 → index 1 (reach covers up to index 4), then index 1 → index 4. Two jumps.

Example 3

Input: nums = [0]
Output: 0
Note: Already on the last index — zero jumps.

Constraints

1 ≤ nums.length ≤ 10⁴
0 ≤ nums[i] ≤ 1000
It is guaranteed you can reach the last index
From index i you may jump to any index in [i+1, i+nums[i]]

Clarifying questions4First question: Must I jump exactly nums[i], or up to nums[i]?Explore questions

Q1.Must I jump exactly nums[i], or up to nums[i]?
Up to — any length from 1 to nums[i]. That 'up to' makes the set of indices reachable in k jumps a contiguous window, which the greedy exploits.
Q2.Is reaching the last index always possible?
Yes, the problem guarantees it. So unlike Jump Game I, I never return -1 or handle a stuck state.
Q3.If the array has one element, what's the answer?
0 — you're already on the last index, no jumps needed. The loop-to-n−1 bound handles this naturally.
Q4.Can I overshoot the last index?
Yes, a jump that lands at or beyond n−1 counts as reaching it. We clamp ranges to n−1 in the DP and stop the greedy loop early.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

Counting a jump at every index instead of only when the cursor reaches the current window's end, or looping to n and double-counting a jump when the last index coincides with curEnd.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Dynamic Programming — Min Jumps to Each Index	`O(n²)`	`O(n)`	Lead with this to show you can model min-jumps formally as a recurrence, then flag the O(n²) range scan as the cost to eliminate.	Read
2	Greedy — BFS Over Contiguous Levels (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Frame it as 'BFS where each level is a contiguous window, so I replace the queue with curEnd and farthest' and justify why a window scan equals a BFS layer.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Dynamic Programming — Min Jumps to Each Index

TimeO(n²)SpaceO(n)

Lead with this to show you can model min-jumps formally as a recurrence, then flag the O(n²) range scan as the cost to eliminate.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Let dp[i] be the minimum jumps to reach index i. dp[0] = 0. How does reaching i depend on earlier indices?

2Hint 2Explore hint

From index i you can extend to any j in [i+1, i+nums[i]] with one more jump, so dp[j] = min(dp[j], dp[i] + 1).

3Hint 3Explore hint

Sweep left to right, relaxing each index's reachable range. The answer is dp[n−1].

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

i=0 (dp=0)

reach [1,2]; dp[1]=1, dp[2]=1

Statedp = [0,1,1,∞,∞]

Final result2

C · Code with teaching comments

Reference implementation previewpublic int jump(int[] nums) { int n = nums.length; int[] dp = new int[n]; Arrays.fill(dp, Integer.MAX_VALUE); dp[0] = 0;Explore the full code

solution.javaJava

Dynamic Programming — Min Jumps to Each Index — reference

5 teaching notes

1
public int jump(int[] nums) {
2
    int n = nums.length;
3
    int[] dp = new int[n];
4
    // Unreached indices start at infinity; only relaxations bring them down.
5
    Arrays.fill(dp, Integer.MAX_VALUE);
6
    // We begin on index 0 with zero jumps spent — the base case.
7
    dp[0] = 0;
8
    for (int i = 0; i < n; i++) {
9
        if (dp[i] == Integer.MAX_VALUE) continue;
10
        // Clamp the reachable range to the array's last index.
11
        int far = Math.min(i + nums[i], n - 1);
12
        for (int j = i + 1; j <= far; j++) {
13
            // Reaching j via i costs one more jump than reaching i — keep the smallest
14
            // such cost.
15
            dp[j] = Math.min(dp[j], dp[i] + 1);
16
        }
17
    }
18
    // Minimum jumps to the last index — the whole question.
19
    return dp[n - 1];
20
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.20 lines

D · Why it works and complexityO(n²) timeO(n) spaceOpen the invariant and proofExplore the proof

ComplexityO(n²) time, O(n) space — For each of n indices we relax up to its full jump range (length up to nums[i]), so the worst case is O(n²) time; the dp array uses O(n) space.

E · Edge cases and pitfalls5nums = [0] — n=1, dp[0]=0, loop relaxes nothing (range empty), returns dp[0]=0.Explore edge cases

Edge cases handled

nums = [0]n=1, dp[0]=0, loop relaxes nothing (range empty), returns dp[0]=0.
nums = [1, 1, 1, 1]Each index reaches only the next, so dp = [0,1,2,3]; returns 3.

Pitfalls

Forgetting to clamp i + nums[i] to n−1 — out-of-bounds writes on large jump values.
Relaxing from an index whose dp is still infinity — propagates garbage (guard with the continue).
Shipping O(n²) when n = 10⁴ makes the linear greedy clearly preferable.

03.2

Approach 2 of 2 · Optimal

Greedy — BFS Over Contiguous Levels (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Frame it as 'BFS where each level is a contiguous window, so I replace the queue with curEnd and farthest' and justify why a window scan equals a BFS layer.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Think BFS: level 0 is index 0, level 1 is everything reachable in one jump, level 2 in two jumps, and so on. The answer is the level number of the last index.

2Hint 2Explore hint

3Hint 3Explore hint

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Interactive diagram

BFS levels as contiguous windows

i=0

Active call / nodeSupporting contextReturned stateNot active

Each jump count is a BFS layer; 'jump up to k' makes every layer a gap-free interval, so two integers replace the queue.

Final result2

C · Code with teaching comments

solution.javaJava

Greedy — BFS Over Contiguous Levels (Optimal) — optimal

5 teaching notes

1
public int jump(int[] nums) {
2
    // jumps = BFS depth so far, curEnd = current level's right edge, farthest = next
3
    // level's reach.
4
    int jumps = 0, curEnd = 0, farthest = 0;
5
    // Stop at n−2 so landing on the last index doesn't trigger a phantom extra jump.
6
    for (int i = 0; i < nums.length - 1; i++) {
7
        // Extend how far the CURRENT level can reach — the next level's boundary.
8
        farthest = Math.max(farthest, i + nums[i]);
9
        // Cursor reached the end of this level → all of it explored, one more jump is
10
        // required to continue.
11
        if (i == curEnd) {
12
            jumps++;
13
            curEnd = farthest;
14
        }
15
    }
16
    return jumps;
17
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.17 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6nums = [0] — Loop runs for i in range(0) — never executes — so jumps stays 0. Already on the last index.Explore edge cases

Edge cases handled

nums = [0]Loop runs for i in range(0) — never executes — so jumps stays 0. Already on the last index.
nums = [2, 1]i=0: farthest=2, i==curEnd → jumps=1, curEnd=2; loop ends (n−1=1). Returns 1.
nums = [1, 2, 1, 1, 1]Levels: [0]→[1]→[2,3]→[4]; cursor hits each curEnd, yielding 3 jumps.

Pitfalls

Looping to n instead of n−1 — double-counts a jump when the last index equals curEnd.
Incrementing jumps at every index rather than only when i reaches curEnd.
Overwriting farthest = i + nums[i] without the max — a small later jump shouldn't shrink the next level's reach.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Counting a jump per index

All indices inside the current window sit at the same BFS depth. Incrementing jumps for each of them counts steps you never took — the count balloons far above the true minimum.

Explore the code comparison

Don't write this

jumps = 0
for i in range(len(nums) - 1):
    farthest = max(farthest, i + nums[i])
    jumps += 1            # wrong: counts every index

Write this instead

jumps = 0
for i in range(len(nums) - 1):
    farthest = max(farthest, i + nums[i])
    if i == cur_end:      # only at the window boundary
        jumps += 1
        cur_end = farthest

Looping to n instead of n−1

If the last index equals curEnd, iterating onto it fires one more jumps++ for a jump that never happens — you're already standing on the goal.

Explore the code comparison

Don't write this

for (int i = 0; i < nums.length; i++) { // includes last index
    farthest = Math.max(farthest, i + nums[i]);
    if (i == curEnd) { jumps++; curEnd = farthest; }
}

Write this instead

for (int i = 0; i < nums.length - 1; i++) {
    farthest = Math.max(farthest, i + nums[i]);
    if (i == curEnd) { jumps++; curEnd = farthest; }
}

Letting a small jump shrink the next level

Assigning farthest = i + nums[i] without the max can pull the next level's boundary backward when a later index has a tiny value, undercounting reach and inflating jumps.

Explore the code comparison

Don't write this

farthest = i + nums[i]; // overwrites a bigger earlier reach

Write this instead

farthest = Math.max(farthest, i + nums[i]);

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Greedy BFS levels — current window end + farthest reach

Code pattern to memorize

jumps = 0; curEnd = 0; farthest = 0
for i in range(n - 1):          # stop before the last index
    farthest = max(farthest, i + nums[i])
    if i == curEnd:             # finished this jump's reachable window
        jumps += 1
        curEnd = farthest        # window expands to the next level
return jumps

Rules to remember

1Think in levels: indices reachable in exactly k jumps are a contiguous window — BFS over the array, no explicit queue.
2Carry `farthest` = the furthest index the current window can reach, updated at every index you pass.
3Carry `curEnd` = the right edge of the current level; when i == curEnd you've exhausted this jump's reach, so `jumps++` and set curEnd = farthest.
4Loop only to `n − 1`, never n — landing on the last index shouldn't trigger one extra phantom jump.
5You never need to know which index you jumped to inside a window — only how far the whole window reaches, which is why greedy = BFS here.
6The problem guarantees reachability, so you don't handle the stuck case (that's Jump Game I).

Use this pattern when

Minimum steps / shortest path on a line where each position grants a forward range
Reachable-in-k-moves sets form contiguous windows (jump *up to* k)
You want BFS's shortest-path guarantee without building a graph
Only the count of jumps matters, not the exact path

Choose another pattern when

Edge weights vary (cost per jump differs) → Dijkstra, not uniform BFS levels
Jumps can go backward or to arbitrary targets → real graph BFS with a queue
You must return the actual jump sequence → augment with parent pointers
Only feasibility (yes/no), not the count → Jump Game I's single-frontier greedy

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Jump Game
Feasibility only (can you reach the end?) — single farthest frontier, no jump counting.
Jump Game III
Coming soon
Jumps go i±nums[i] to a zero — true graph BFS/DFS, levels are no longer contiguous.
Jump Game IV
Coming soon
Jump ±1 or to equal-valued indices — explicit BFS with a queue and value-buckets.
Minimum Number of Taps to Open to Water a Garden
Coming soon
Same min-jumps-as-BFS-windows greedy, reframed as covering an interval with ranges.

Same pattern

←

Jump Game

Continue · Next problem

Gas Station