Generated by Codex with GPT-5

Quick facts

• Difficulty: MEDIUM
• Problem: Jump Game II
• Main tags: Array, Dynamic Programming, Greedy

What the problem is really asking

Each position tells how far forward it can jump. The goal is not to maximize distance on each move. The goal is to reach the last index using as few jumps as possible.

That makes this a shortest-path problem on an implicit graph:

• from index i, there are edges to i + 1, i + 2, …, i + nums[i]
• every edge has equal cost because each jump counts as exactly one move

Thinking about it this way is useful because “minimum number of jumps” usually suggests BFS. The main trick is realizing that a full graph traversal is unnecessary because the graph has a very regular structure.

A first correct solution

The most direct dynamic programming idea is:

dp[i] = minimum jumps needed to reach index i

Then for each index i, try all earlier positions j that can reach i, and compute:

dp[i] = min(dp[j] + 1)

That is correct, but it takes O(n^2) time in the worst case because many reachability relationships are checked repeatedly.

This version is still useful in an interview because it proves the candidate understands the problem before optimizing it.

The key insight that leads to the optimal solution

Suppose all indices in some range are reachable using exactly k jumps. While scanning that range, each index offers some farther place that can be reached in one more jump.

So instead of choosing the next landing position immediately, it is better to ask:

what is the farthest index reachable using k + 1 jumps from anywhere in the current range?

That turns the problem into scanning layers:

• the current layer is every index reachable with the current jump count
• the next layer ends at the farthest position any index in the current layer can reach

Once the scan reaches the end of the current layer, one more jump is unavoidable. At that moment, the best thing to do is commit to the entire next layer by extending the boundary to the farthest reachable index seen so far.

This is exactly BFS on the implicit graph, but compressed into two integers instead of an explicit queue.

Why the greedy boundary update is optimal

The greedy step is not “jump to the locally farthest index.” That version is not reliable.

The real greedy rule is:

while scanning all positions reachable in the current number of jumps, keep track of the farthest place reachable in one additional jump

This works because all indices inside the current layer are equally good in terms of jump count: they are all reachable in exactly the same number of moves. If the algorithm has already paid k jumps to enter the layer, then any optimal solution must pay jump k + 1 to leave it unless the target is already inside the layer.

So when the current layer ends, the only question that matters is how far the next layer can extend. Choosing the farthest boundary preserves every best future possibility, and no alternative choice can use fewer jumps because all alternatives still consume that same next jump.

Best approach

For this problem, the optimal interview answer is the greedy level-scan approach:

• Time: O(n)
• Space: O(1)

It is fast because each index is processed once, and it is easy to justify once the problem is reframed as BFS over ranges.

Python solution

The implementation below keeps two boundaries:

• current_jump_end: the farthest index reachable with the current number of jumps
• farthest_reachable: the farthest index reachable after taking one more jump from anywhere inside the current layer

Whenever the scan reaches current_jump_end, it has finished one BFS layer, so it increments the jump count and moves the boundary out to farthest_reachable.

from typing import List


def minimum_jumps_to_reach_end(nums: List[int]) -> int:
    """
    Return the minimum number of jumps needed to reach the last index.

    The input is guaranteed to be reachable, which matches the LeetCode
    problem statement.
    """
    last_index = len(nums) - 1

    if last_index <= 0:
        return 0

    jumps_taken = 0
    current_jump_end = 0
    farthest_reachable = 0

    # The last index does not need to be expanded because reaching or passing
    # it means the answer is already known.
    for current_index in range(last_index):
        farthest_reachable = max(
            farthest_reachable,
            current_index + nums[current_index],
        )

        # Finishing the current layer means one more jump is required.
        if current_index == current_jump_end:
            jumps_taken += 1
            current_jump_end = farthest_reachable

            if current_jump_end >= last_index:
                break

    return jumps_taken


class Solution:
    def jump(self, nums: List[int]) -> int:
        """LeetCode entry point."""
        return minimum_jumps_to_reach_end(nums)

Interview follow-ups

What changes if the array is not guaranteed to be reachable?

The same greedy scan still works, but it needs one extra failure check. If the scan reaches the end of the current layer and farthest_reachable has not moved beyond that boundary, then the algorithm is stuck: there is no valid next jump, so the last index cannot be reached. In code, that usually means checking whether current_index == current_jump_end == farthest_reachable before incrementing the jump count. The running time stays O(n) and the extra space stays O(1). The only difference is that the function now needs to return a sentinel such as -1 or raise an exception depending on the surrounding API.

How would you return one actual minimum-jump path, not just the count?

The cleanest interview answer is to keep parent information for the first time each index is discovered in the BFS layering process. Because BFS discovers nodes in increasing jump count, the first parent recorded for an index already belongs to a minimum-jump path. After the scan finishes, backtrack from the last index through the parent array to reconstruct the path. This keeps the logic conceptually simple and still processes each index only once, so the time complexity remains O(n). The tradeoff is space: reconstructing the path needs O(n) extra memory, whereas the count-only version needs constant extra space.

Can this be solved with dynamic programming instead of greedy?

Yes. A standard DP solution defines dp[i] as the minimum jumps needed to reach index i, initializes dp[0] = 0, and for each i checks every earlier j that can reach it. That solution is easy to derive and can be a good stepping stone during an interview because it makes the state transition explicit. However, it takes O(n^2) time in the worst case, which is much slower than the greedy level-scan solution. The tradeoff is simplicity of first derivation versus final efficiency.

Why is this often described as BFS even though there is no queue?

Because the algorithm is still exploring the implicit graph one jump count at a time. The interval from the previous boundary to current_jump_end is exactly one BFS level: every index in that range is reachable with the same number of jumps. Scanning that level and computing farthest_reachable is equivalent to expanding all nodes in the queue for that level and collecting the next frontier. The queue disappears only because the graph’s edges point forward in contiguous ranges, so the frontier can be summarized by boundaries instead of storing every node explicitly. That preserves the BFS correctness argument while reducing space to O(1).

Takeaway

The right mental model is “BFS over ranges, implemented greedily.” Once that clicks, the algorithm becomes short: scan the current reachable layer, record how far the next jump could take you, and increase the jump count only when the current layer is exhausted.