Jump Game II

Free with account Updated Nov 19, 2026 · 5 min read
On this page

    Problem statement

    You start at index 0 of an array of non-negative integers. The value at each index is the longest jump you may make from there (you can also jump shorter). Return the minimum number of jumps needed to reach the last index. The input guarantees the last index is reachable.

    The follow-up to Jump Game: there the question was "can you reach the end?", here it's "how fast?". It is a shortest path in disguise, and the trick is to run a BFS without building a graph. Original problem: LeetCode 45.

    Example

    The shortest route takes 3 jumps; the longest first jump would land on a 1 and waste a move.
    The shortest route takes 3 jumps; the longest first jump would land on a 1 and waste a move.
    Input:  [2, 4, 1, 1, 3, 1, 1]
    Output: 3        # 0 -> 1 -> 4 -> 6  (or 0 -> 1 -> 5 -> 6)
    Input:  [1, 1, 1]
    Output: 2
    Input:  [0]
    Output: 0        # already at the last index

    Constraints (assumed)

    • 1 ≤ n ≤ 10⁴; 0 ≤ nums[i] ≤ 1,000.
    • The last index is always reachable.

    What this question tests

    • Seeing the problem as a shortest path where every edge costs one jump.
    • Replacing an explicit BFS with windows of indices ("everything reachable in j jumps").
    • Not being fooled by the tempting greedy "always jump as far as possible".

    Questions to ask first

    1. Is the end always reachable? (Here: yes. Otherwise return −1, and the code must detect a stuck window.)
    2. Can I jump shorter than the value? (Here: yes, any length from 1 to nums[i].)
    3. Do you need the path or just the count? (Here: the count.)
    4. How large is n? O(n²) DP is fine for small n, not for 10⁴ with big values.