Jump Game II medium

Description

You’re given an integer array nums. Starting at index 0, nums[i] is the maximum jump length from i. Return the minimum number of jumps to reach the last index. You may assume you can always reach it.

Examples

> Case 1:
    nums = [2, 3, 1, 1, 4]
    Output: 2
    # 0 → 1 (jump 1 step) → 4 (jump 3 steps).
 
> Case 2:
    nums = [2, 3, 0, 1, 4]
    Output: 2

Constraints

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

Greedy intuition — BFS in disguise

This is fundamentally a shortest-path problem on an unweighted graph where each node is an array index and edges go to all j you can jump to. BFS would give the answer in O(N²).

The greedy speedup: instead of explicitly running BFS, track the boundary of the current “BFS layer” and decide when to advance to the next layer.

We're at "layer L" — the set of indices reachable in exactly L jumps.
The layer is the interval [layer_start, layer_end].
While scanning within this interval, compute the "farthest" index we
can reach in L+1 jumps.

When we hit layer_end, we MUST jump (otherwise we'd be stuck).
Increment jumps, set the new layer's range to [old_end + 1, farthest].
Repeat.

This collapses the BFS into a linear scan with O(1) state.

Code

int jump(vector<int>& nums) {
    int n = nums.size();
    int jumps = 0, current_end = 0, farthest = 0;
    for (int i = 0; i < n - 1; i++) {        // n-1: don't need to jump from last index
        farthest = max(farthest, i + nums[i]);
        if (i == current_end) {              // reached the end of current layer
            jumps++;
            current_end = farthest;
            if (current_end >= n - 1) break;
        }
    }
    return jumps;
}

def jump(nums):
    n = len(nums)
    jumps = current_end = farthest = 0
    for i in range(n - 1):                   # skip last index
        farthest = max(farthest, i + nums[i])
        if i == current_end:                 # must jump at boundary
            jumps += 1
            current_end = farthest
            if current_end >= n - 1: break
    return jumps

public int jump(int[] nums) {
    int n = nums.length;
    int jumps = 0, currentEnd = 0, farthest = 0;
    for (int i = 0; i < n - 1; i++) {
        farthest = Math.max(farthest, i + nums[i]);
        if (i == currentEnd) {
            jumps++;
            currentEnd = farthest;
            if (currentEnd >= n - 1) break;
        }
    }
    return jumps;
}

Trace on [2, 3, 1, 1, 4]

i=0: farthest = max(0, 0+2) = 2.
     i == current_end (0)  →  jumps=1, current_end=2.

i=1: farthest = max(2, 1+3) = 4.
     i != current_end (2).

i=2: farthest = max(4, 2+1) = 4.
     i == current_end (2)  →  jumps=2, current_end=4.
     current_end >= n-1 (4)  →  break.

Return 2.

Two jumps. ✓

Why “always jump as far as possible” isn’t quite right

You might think: “from each position, just jump to wherever i + nums[i] is max.” That’s the wrong greedy and gives wrong answers — because the longest single jump from index i might lead to a position from which you can’t make much progress.

The correct greedy is: defer the jump decision until you’re forced to. While walking through the current layer, you see all reachable positions in the next layer and can compute the farthest one. Then you jump.

This subtle difference is the heart of why the BFS-layered approach works.

Compare with Jump Game I

The two problems share the farthest reach idea, but:

• Jump I: “Can we reach the end?” — only need to know if farthest >= n-1 ever. No jump-counting.
• Jump II: “Minimum jumps?” — need to know when to increment the jump count, which requires tracking the layer boundary.

Different questions, same insight (farthest), different bookkeeping (layer ends).

A neat trick: BFS without an explicit queue

This is one of the cleanest examples of an algorithm that logically is BFS but is implemented without ever materializing a queue. The “layer” is implicit in the index range [current_end_prev + 1, current_end]. The “frontier” is the max-reach value we accumulate.

The same pattern shows up in:

• Shortest path with bounded weight problems.
• Level-order traversal of an implicit tree.
• Some 0-1 BFS variants we cover on Day 10.

When you see “layer by layer” with cheap-to-compute frontiers, this implicit-BFS pattern often beats an explicit queue.

Analysis

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

Beats the O(N²) BFS and the O(N²) DP solution by a wide margin.