Fewest Jumps to Reach the End

medium array greedy bfs

Problem

Each entry is the maximum forward jump from that index. Find the minimum number of jumps from index 0 to the last index, assuming the end is reachable. Treat indices like BFS layers: the current jump can land anywhere within currentEnd; while exploring it, peek how far the next jump could reach. When i reaches currentEnd, you must jump — increment the count and adopt the peeked frontier as the new boundary.

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;
}

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