Jump Game II [Medium] — Greedy BFS-Level Jumps

Problem Statement

Given nums[i] = maximum jump length at index i, return the minimum number of jumps to reach the last index. You can always reach the end.

Input: [2,3,1,1,4] → Output: 2

Intuition

Think of it as BFS levels. Track the current jump boundary (curEnd) and the furthest reachable index (farthest). When we hit curEnd, we must jump — increment jumps and update curEnd = farthest.

Solutions

C++

int jump(vector<int>& nums) {
    int jumps=0, curEnd=0, farthest=0;
    for (int i=0; i<nums.size()-1; i++) {
        farthest = max(farthest, i+nums[i]);
        if (i == curEnd) { jumps++; curEnd = farthest; }
    }
    return jumps;
}

Java

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

JavaScript

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

Python

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

Complexity

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