Minimum number of jumps to reach the end

Medium

Problem

You start at index 0. arr[i] is the maximum number of steps you can jump forward from index i. Return the minimum number of jumps needed to reach the last index, or −1 if it cannot be reached.

Example 1

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

Jump 0 → 1 (1 step), then 1 → 4 (3 steps).

Example 2

Input:  [1, 0, 3]
Output: -1

Index 1 has value 0, so you are stuck.

Also asked as: Minimum no. of Jumps to reach end of an array · Minimum number of jumps to reach end

Test cases

Case 1

Input:    [2,3,1,1,4]
Expected: 2

Case 2

Input:    [1,3,5,8,9,2,6,7,6,8,9]
Expected: 3

Case 3

Input:    [1,0,3]
Expected: -1

Case 4

Input:    [0]
Expected: 0

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Greedy (BFS levels)

Time O(n)Space O(1)

Each "jump" covers a range; extend `farthest` while scanning it, and when you reach the current range end, take a jump.

function minJumps(a) {
let jumps = 0, curEnd = 0, farthest = 0;
for (let i = 0; i < a.length - 1; i++) {
farthest = Math.max(farthest, i + a[i]);
if (i === curEnd) {
if (farthest <= i) return -1; // stuck
jumps++;
curEnd = farthest;
}
}
return jumps;
}