Jump Game II — Minimum Jumps with the Greedy Window Technique

Problem Statement#

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. Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can always reach nums[n - 1].

Constraints:

• 1 <= nums.length <= 10^4
• 0 <= nums[i] <= 1000
• The answer is guaranteed to exist.

Example 1:

Input:  nums = [2, 3, 1, 1, 4]
Output: 2
Explanation: Jump from index 0 to index 1 (jump of 2 from nums[0]=2... or just 1),
             then jump from index 1 to the last index. Minimum = 2 jumps.

Example 2:

Input:  nums = [2, 3, 0, 1, 4]
Output: 2
Explanation: Jump from index 0 to index 1, then jump from index 1 to the last index.

Example 3:

Input:  nums = [1, 2, 3]
Output: 2
Explanation: Jump from 0 to 1, then 1 to 2. Two jumps.

Why This Problem Matters#

Jump Game II (LeetCode 45) is the natural extension of Jump Game (LC 55): instead of asking if the last index is reachable, it asks for the minimum number of jumps to get there. This upgrade transforms a reachability problem into an optimization problem, and the optimal solution requires a more subtle greedy argument.

Amazon and Google interviewers use this problem to test whether candidates can move from "can I reach?" (Jump Game I) to "how cheaply can I reach?" (Jump Game II) using the same greedy framework. The DP solution with O(n^2) time is a necessary stepping stone to justify the O(n) greedy, and interviewers expect candidates to show both.

The "window boundary" greedy technique used here — extending a current reachable window and counting jumps when you exhaust it — is a pattern that surfaces in scheduling problems, sliding window variants, and range coverage problems.

The Core Insight#

Think of jumps as expanding coverage windows:

• Window 0 covers just index 0 (you start here, 0 jumps used).
• Window 1 covers all indices reachable in exactly 1 jump from any position in Window 0.
• Window 2 covers all indices reachable in exactly 2 jumps from any position in Window 1.
• And so on.

This is essentially BFS on an implicit graph, but implemented without a queue using two boundary variables.

Greedy approach:

• jumps: number of jumps taken so far
• curr_end: the furthest index reachable with jumps jumps (the current window's right boundary)
• farthest: the furthest index reachable with jumps + 1 jumps (the next window's right boundary)

Scan from left to right. At each index i:

1. Update farthest = max(farthest, i + nums[i]) — expand the next window.
2. When i == curr_end (you have reached the current window's boundary): increment jumps and set curr_end = farthest — move to the next window.

Return jumps when the loop ends.

Why stop at n - 2: Once you reach the last index, you are done. If curr_end >= n - 1 before the loop ends, you need not increment jumps again. Scanning only through n - 2 avoids an extra (unnecessary) jump count.

Building the DP Solution#

Step 1 — Naive DP (O(n^2))#

# Python — naive DP, O(n^2) — illustrative
def jump(nums):
    n = len(nums)
    dp = [float('inf')] * n
    dp[0] = 0
    for i in range(1, n):
        for j in range(i):
            if j + nums[j] >= i and dp[j] != float('inf'):
                dp[i] = min(dp[i], dp[j] + 1)
    return dp[n - 1]

// JavaScript — naive DP, O(n^2)
function jump(nums) {
    const n = nums.length;
    const dp = new Array(n).fill(Infinity);
    dp[0] = 0;
    for (let i = 1; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (j + nums[j] >= i && dp[j] !== Infinity) {
                dp[i] = Math.min(dp[i], dp[j] + 1);
            }
        }
    }
    return dp[n - 1];
}

dp[i] = minimum jumps to reach index i. For each i, check all positions j that can reach i. O(n^2) due to inner loop.

Step 2 — Top-Down Memoization (O(n^2) time, O(n) space)#

# Python — top-down memoization
from functools import lru_cache
 
class Solution:
    def jump(self, nums: list[int]) -> int:
        n = len(nums)
 
        @lru_cache(maxsize=None)
        def dp(i: int) -> int:
            if i == 0:
                return 0
            best = float('inf')
            for j in range(i):
                if j + nums[j] >= i:
                    result = dp(j)
                    if result != float('inf'):
                        best = min(best, result + 1)
            return best
 
        return dp(n - 1)

// JavaScript — top-down memoization
var jump = function(nums) {
    const n = nums.length;
    const memo = new Map();
 
    function dp(i) {
        if (i === 0) return 0;
        if (memo.has(i)) return memo.get(i);
        let best = Infinity;
        for (let j = 0; j < i; j++) {
            if (j + nums[j] >= i) {
                const sub = dp(j);
                if (sub !== Infinity) best = Math.min(best, sub + 1);
            }
        }
        memo.set(i, best);
        return best;
    }
 
    return dp(n - 1);
};

Step 3 — Greedy Window Technique (O(n) time, O(1) space)#

# Python — greedy window, O(n) time, O(1) space
class Solution:
    def jump(self, nums: list[int]) -> int:
        jumps = 0
        curr_end = 0
        farthest = 0
 
        for i in range(len(nums) - 1):  # stop at n-2
            farthest = max(farthest, i + nums[i])
            if i == curr_end:
                jumps += 1
                curr_end = farthest
 
        return jumps

// JavaScript — greedy window, O(n) time, O(1) space
var jump = function(nums) {
    let jumps = 0, currEnd = 0, farthest = 0;
    for (let i = 0; i < nums.length - 1; i++) {
        farthest = Math.max(farthest, i + nums[i]);
        if (i === currEnd) {
            jumps++;
            currEnd = farthest;
        }
    }
    return jumps;
};

Optimized Solution#

The greedy window technique is the optimal solution. No further optimization is needed:

# Python — final solution
class Solution:
    def jump(self, nums: list[int]) -> int:
        jumps = curr_end = farthest = 0
        for i in range(len(nums) - 1):
            farthest = max(farthest, i + nums[i])
            if i == curr_end:
                jumps += 1
                curr_end = farthest
        return jumps

// JavaScript — final solution
var jump = function(nums) {
    let jumps = 0, currEnd = 0, farthest = 0;
    for (let i = 0; i < nums.length - 1; i++) {
        farthest = Math.max(farthest, i + nums[i]);
        if (i === currEnd) {
            jumps++;
            currEnd = farthest;
        }
    }
    return jumps;
};

Visual Dry Run#

Input: nums = [2, 3, 1, 1, 4], n = 5

Answer: 2. Jump from index 0 to index 1 (jump 1), then from index 1 to index 4 (jump 2).

Window breakdown:

• Window 0 (0 jumps): [0]
• Window 1 (1 jump): [1, 2] — reachable from index 0 with nums[0]=2
• Window 2 (2 jumps): [3, 4] — reachable from indices 1 or 2

Last index (4) is in window 2 — answer is 2.

Complexity Analysis#

Common Mistakes#

1. Including the last index in the loop. The loop runs from 0 to n - 2 (exclusive of last). If you include index n - 1, you may increment jumps one extra time when i == curr_end == n - 1. Stop at n - 2.

2. Updating curr_end immediately when farthest is updated. curr_end updates only when i == curr_end (window boundary reached), not on every farthest update. Confusing these two updates breaks the algorithm.

3. Initializing curr_end to nums[0] instead of 0. Initialize curr_end = 0. The first window boundary is at index 0. When i reaches 0, jumps increments and curr_end = farthest (which at that point equals nums[0]).

4. Returning jumps + 1 or jumps - 1. The algorithm increments jumps exactly when you move to a new window. After scanning through n - 2 indices, jumps holds the exact answer.

5. Using BFS with a queue unnecessarily. The greedy window technique is equivalent to BFS without the queue overhead. Do not use an explicit BFS queue for this problem in interviews — the greedy is cleaner.

6. Not handling n = 1. When n = 1, you start at the last index and need 0 jumps. The loop range(n - 1) = range(0) does not execute, and jumps = 0 is returned correctly.

Interview Tips#

Present the DP first. "I can define dp[i] as the minimum jumps to reach index i. dp[0] = 0. For each i, I check all positions j that can reach i: dp[i] = min(dp[j] + 1). This is O(n^2)." This shows the DP foundation.

Motivate the greedy upgrade. "Notice I don't need to check all previous positions — I just need the furthest any reachable position can reach. I can compress this to a window boundary check."

Explain the window analogy. "Think of jumps as BFS layers. Within one jump, you can reach a window of positions. When you exhaust that window, one more jump expands to the next window. I track curr_end (current window boundary) and farthest (next window boundary)."

Distinguish from Jump Game I. "Jump Game I asks: is the last index reachable? Jump Game II asks: how many jumps minimum? Same greedy idea, but II counts window transitions."

Follow-up Questions#

Q: What if some indices have value 0 (you cannot move from there)? The greedy handles this naturally — a zero does not extend farthest, so you still rely on other positions in the current window to extend reach.

Q: What if you need to output the actual jump sequence? Track parent[i] = j for the position j from which you should jump to reach i optimally. Reconstruct by following parent pointers from n-1 to 0.

Q: What if you can also jump backward (negative jumps)? The greedy no longer works. Use BFS from index 0 with both forward and backward edges to find the shortest path to index n-1.

Q: What if each jump has a cost and you want minimum cost, not minimum jumps? This becomes a shortest-path problem. Use Dijkstra's algorithm with edge weights equal to the jump costs. The greedy does not directly extend to weighted jumps.

Q: What is the relationship to Jump Game I? Jump Game I: return max_reach >= n - 1 after one pass. Jump Game II: count how many times you need to extend the window to cover index n - 1.

Key Takeaways#

• Jump Game II minimizes the number of jumps to reach the last index using a greedy window technique.
• Maintain three variables: jumps (count), curr_end (current window right boundary), farthest (next window right boundary). Increment jumps when you hit curr_end, then set curr_end = farthest.
• Loop from 0 to n - 2 (stop before the last index) to avoid an extra jump count.
• The DP approach (O(n^2)) is instructive but suboptimal — always upgrade to the greedy window (O(n) O(1)) for interviews.
• The greedy is equivalent to layered BFS on an implicit graph: each layer is one additional jump, and you expand to the farthest reachable position in each layer.
• Jump Game (reachability) and Jump Game II (minimum jumps) share the same greedy farthest tracking — understanding both together deepens the pattern.