Jump Game II

MediumGreedy · Implicit BFS🧩 Greedy LeetCode #45 ↗Updated Oct 30, 2026

Problem

You stand at index 0 of an array nums, where nums[i] is the maximum number of steps you may jump forward from index i (any shorter jump is also allowed). Return the fewest jumps needed to land on the last index. The last index is guaranteed to be reachable.

Input[2,3,1,1,4]Output2

Input[2,3,0,1,4]Output2

1 ≤ n ≤ 10⁴ · 0 ≤ nums[i] ≤ 1000 · the last index is always reachable

Try it yourself

Java

class Solution {
    public int jump(int[] nums) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Indices reachable with exactly k jumps form a contiguous window. Treat each window as a BFS level: while scanning it, track the farthest index any of its cells can reach — that becomes the right edge of the next level.

PatternGreedy

Instinct An optimisation where one obvious local rule (earliest end, farthest reach, biggest first) never needs undoing - commit to it, then try hard to break it.

Memory hack Grab the best bite now and never look back - but only once a counterexample hunt fails to make you regret it.

Open the Greedy guide →

Approaches

Brute ForceRecursion over Every Jump Length

Time O(2ⁿ)Space O(n)

From index i, try every jump length 1..nums[i] and take 1 + min over the results; reaching the last index costs 0. It explores every path, so it is correct, but the same suffixes are recomputed over and over.

Java

public int jump(int[] nums) {
    return minJumps(nums, 0);
}

private int minJumps(int[] nums, int i) {
    int n = nums.length;
    if (i == n - 1) return 0;
    int best = Integer.MAX_VALUE;
    for (int j = i + 1; j <= Math.min(n - 1, i + nums[i]); j++) {
        int sub = minJumps(nums, j);
        if (sub != Integer.MAX_VALUE) best = Math.min(best, sub + 1);
    }
    return best;   // MAX_VALUE = last index unreachable from i
}

Clear recurrence, but exponential — only usable for tiny arrays.

Better1-D DP (Relax Forward)

Time O(n²)Space O(n)

Let dp[i] be the fewest jumps to reach i. Going left to right, every index j in i+1..i+nums[i] can be reached in dp[i] + 1. Each state is solved once, removing the recursion's repeated work.

Java

public int jump(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;   // i not reachable
        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];
}

Polynomial and safe, but still quadratic when jump lengths are large.

OptimalGreedy BFS Levels

Time O(n)Space O(1)

end is the right edge of the current level, far the farthest reach seen so far. When i hits end, the level is exhausted: one more jump is forced, and the next level extends to far. The loop stops before the last index so no extra jump is counted.

Java

public int jump(int[] nums) {
    int jumps = 0, end = 0, far = 0;
    for (int i = 0; i < nums.length - 1; i++) {
        far = Math.max(far, i + nums[i]);   // best reach from this level
        if (i == end) {                     // level exhausted: must jump
            jumps++;
            end = far;
        }
    }
    return jumps;
}

Dry run[2,3,1,1,4]

i ie endf far changed

i=0
2
i
3

1
e f
1

4

far=2, i==end → jumps=1
i=1
2

3
i
1
e
1

4
f
far=max(2,4)=4
i=2
2

3

1
i
1

4
e f
i==end → jumps=2, end=4
i=3
2

3

1

1
i
4
e f
far=4; loop ends → 2 ✔

One pass, constant memory — the expected interview answer.

Pro tip

Looping to n-2 matters: at i = n-1 you are already done, and i == end there would add a phantom jump.

At a glance

Level	Approach	Time	Space
Brute Force	Recursion over Every Jump Length	`O(2ⁿ)`	`O(n)`
Better	1-D DP (Relax Forward)	`O(n²)`	`O(n)`
Optimal	Greedy BFS Levels	`O(n)`	`O(1)`

Common pitfalls

Looping to n-1 — counts an extra jump when end lands on the last index.
Always jumping to the largest nums[i] — the best next cell is the one reaching farthest.
Returning 1 for n == 1 — you start on the last index, so the answer is 0.

Interview tips

Frame it as BFS on indices; then show the levels are contiguous, so no queue is needed.
Mention the recursion → DP → greedy progression and each complexity.
Contrast with Jump Game I (55), which only tracks the farthest reach.

Pattern

Greedy range expansion (implicit BFS) → minimum steps when each level is a contiguous interval.

My notes saved in this browser