Jump Game II

medium array greedy bfs

Problem

Given an array of non-negative integers nums, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Your goal is to reach the last index in the minimum number of jumps.

Inputnums = [2, 3, 1, 1, 4]

Output2

Jump 1: 0 → 1. From 1 you can reach index 4 directly. Jump 2: 1 → 4.

nums (non-negative, comma-separated)

def jump(nums):
    jumps = current_end = 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

function jump(nums) {
  let jumps = 0, currentEnd = 0, 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;
}

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

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

Explanation

We want the minimum number of jumps to reach the last index. The greedy idea is like a breadth-first expansion: think of each jump as covering a whole range of reachable indices, and we count how many such ranges we need.

We keep three values: farthest (the furthest index reachable so far), current_end (the boundary of the current jump's range), and jumps (the count). As we scan index i, we update farthest = max(farthest, i + nums[i]) — the best we could reach if we jumped optimally from somewhere in the current range.

When i reaches current_end, it means we have explored everything reachable with the current number of jumps, so we must take another jump: we do jumps += 1 and set current_end = farthest to open up the next range.

Notice the loop stops before the last index — that prevents counting an extra jump if we land exactly on the end.

Example: nums = [2, 3, 1, 1, 4]. From index 0 we can reach up to 2; hitting boundary 0 we jump (jumps=1, end=2). Scanning indices 1 and 2, farthest grows to 1 + 3 = 4. At boundary 2 we jump again (jumps=2, end=4), which already covers the last index. Answer: 2.

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