Jump Game II — LC 45 Greedy BFS Layer Tracking

Problem Statement#

Given a non-negative integer array nums where each element is the maximum jump length from that position, return the minimum number of jumps to reach the last index. You can assume the last index is reachable.

Constraints:

• 1 <= nums.length <= 10^4
• 0 <= nums[i] <= 1000

Input:  nums = [2,3,1,1,4]
Output: 2

Input:  nums = [2,3,0,1,4]
Output: 2

Why This Problem Matters#

LC 45 is a popular array interview question at Amazon, Apple, and Adobe. It tests whether you can recognize a greedy BFS-layer pattern hidden inside what looks like a DP problem. The naive DP is O(n^2); the greedy view delivers O(n).

Because the problem maps cleanly to "shortest path in unweighted graph," it doubles as a teaching moment for BFS thinking on arrays. Mastering the layer-tracking trick prepares you for LC 1306, LC 871, and any "minimum steps" array problem.

The Core Insight#

Treat each index as a node and each nums[i] as edges to indices i+1..i+nums[i]. The minimum number of jumps is the BFS layer that contains n - 1.

Instead of using a queue, track the current layer's farthest reach currentEnd and the next layer's farthest reach farthest. When i hits currentEnd, we have used one more jump and advance currentEnd = farthest.

Visual Dry Run#

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

Loop ends at n - 1 = 4; answer is 2.

Solution (Optimal)#

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

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

Time: O(n) — single pass. Space: O(1).

Common Mistakes#

• Iterating up to n instead of n - 1 and double-counting the last jump.
• Updating jumps when i > currentEnd instead of i == currentEnd.
• Confusing the meaning of currentEnd (boundary of current layer) and farthest (boundary of next layer).
• Solving with O(n^2) DP when interviewer expects O(n).
• Returning farthest instead of jumps.

Interview Tips#

• Frame the array as a graph; the BFS analogy is the cleanest explanation.
• Walk through the index transitions carefully — i == currentEnd is the key event.
• Mention LC 55 (Jump Game I) as the boolean reachability version.
• Note: stop iterating at n - 1 because reaching the last index is the goal.

Follow-up Questions#

• LC 55 Jump Game — boolean reachability with same greedy.
• Minimum jumps with negative steps — BFS with explicit queue.
• Output the jump path itself — track parent pointers.
• Handle unreachable end — return -1 if i > farthest.
• 2D version — minimum moves to reach corner of a grid.

Key Takeaways#

• LC 45 maps to BFS layers in linear time and constant space.
• Track current-layer reach and next-layer reach as two scalars.
• Increment jumps exactly when i hits the boundary of the current layer.
• Iterate up to n - 1, not n, to avoid an extra jump.
• The greedy view is provably optimal for this monotone reachability problem.
• Generalizes to LC 55 boolean reachability.
• DP gives O(n^2); greedy gives O(n) for FAANG-level scoring.