.png)
Minimum Number of Jumps to Reach End
Problem Statement
You are given an integer array arr[] of size n.
Each element arr[i] represents the maximum number of steps you can jump forward from index i.
Return the minimum number of jumps required to reach the last index starting from index 0.
If the end is not reachable, return -1.
Example 1
Input
arr = [2,3,1,1,4]
Output
2
Explanation
Jump from index 0 → 1 → 4
Example 2
Input
arr = [1,1,0,1]
Output
-1
Why This Problem Is Important
Classic greedy interview problem
Tests optimization from brute force to greedy
Used in path & reachability problems
Foundation for interval coverage logic
Very frequently asked in product interviews
Approaches Overview
| Approach | Technique | Time | Space |
|---|---|---|---|
| Approach 1 | Brute Force Recursion | O(2ⁿ) | O(n) |
| Approach 2 | Dynamic Programming | O(n²) | O(n) |
| Approach 3 | Greedy (Optimal) | O(n) | O(1) |
Approach 1: Brute Force Recursion
Idea
From each index, try all possible jumps and find the minimum jumps needed to reach the end.
Algorithm
- Start from index 0
- Try jumps from 1 to arr[i]
- Recursively compute minimum jumps
- Return minimum among all paths
Time & Space Complexity
Time: O(2ⁿ)
Space: O(n) (recursion stack)
C Implementation
#include
#include
int minJumps(int arr[], int n, int idx) {
if (idx >= n - 1)
return 0;
if (arr[idx] == 0)
return INT_MAX;
int min = INT_MAX;
for (int i = 1; i <= arr[idx]; i++) {
int jumps = minJumps(arr, n, idx + i);
if (jumps != INT_MAX && jumps + 1 < min)
min = jumps + 1;
}
return min;
}
int main() {
int arr[] = {2,3,1,1,4};
int n = 5;
int res = minJumps(arr, n, 0);
printf("%d", res == INT_MAX ? -1 : res);
return 0;
}
Output:
2
C++ Implementation
#include
#include
using namespace std;
int minJumps(int arr[], int n, int idx) {
if (idx >= n - 1) return 0;
if (arr[idx] == 0) return INT_MAX;
int ans = INT_MAX;
for (int i = 1; i <= arr[idx]; i++) {
int jumps = minJumps(arr, n, idx + i);
if (jumps != INT_MAX)
ans = min(ans, jumps + 1);
}
return ans;
}
int main() {
int arr[] = {2,3,1,1,4};
int n = 5;
int res = minJumps(arr, n, 0);
cout << (res == INT_MAX ? -1 : res);
}
Output:
2
Java Implementation
class Main {
static int minJumps(int[] arr, int idx) {
if (idx >= arr.length - 1) return 0;
if (arr[idx] == 0) return Integer.MAX_VALUE;
int ans = Integer.MAX_VALUE;
for (int i = 1; i <= arr[idx]; i++) {
int jumps = minJumps(arr, idx + i);
if (jumps != Integer.MAX_VALUE)
ans = Math.min(ans, jumps + 1);
}
return ans;
}
public static void main(String[] args) {
int[] arr = {2,3,1,1,4};
int res = minJumps(arr, 0);
System.out.print(res == Integer.MAX_VALUE ? -1 : res);
}
}
Output:
2
Python Implementation
import sys
def minJumps(arr, idx):
if idx >= len(arr) - 1:
return 0
if arr[idx] == 0:
return sys.maxsize
ans = sys.maxsize
for i in range(1, arr[idx] + 1):
jumps = minJumps(arr, idx + i)
if jumps != sys.maxsize:
ans = min(ans, jumps + 1)
return ans
arr = [2,3,1,1,4]
res = minJumps(arr, 0)
print(-1 if res == sys.maxsize else res)
Output:
2
C# Implementation
using System;
class Program {
static int MinJumps(int[] arr, int idx) {
if (idx >= arr.Length - 1) return 0;
if (arr[idx] == 0) return int.MaxValue;
int ans = int.MaxValue;
for (int i = 1; i <= arr[idx]; i++) {
int jumps = MinJumps(arr, idx + i);
if (jumps != int.MaxValue)
ans = Math.Min(ans, jumps + 1);
}
return ans;
}
static void Main() {
int[] arr = {2,3,1,1,4};
int res = MinJumps(arr, 0);
Console.Write(res == int.MaxValue ? -1 : res);
}
}
Output:
2
Approach 2: Dynamic Programming
Idea
Let dp[i] store the minimum jumps needed to reach index i.
Algorithm
- Initialize dp[0] = 0, rest as infinity
- For each i, update reachable positions
- Answer is dp[n-1]
Time & Space Complexity
Time: O(n²)
Space: O(n)
C++ Implementation
#include
#include
using namespace std;
int main() {
int arr[] = {2,3,1,1,4};
int n = 5;
int dp[n];
dp[0] = 0;
for(int i = 1; i < n; i++)
dp[i] = INT_MAX;
for(int i = 0; i < n; i++) {
if(dp[i] == INT_MAX || arr[i] == 0) continue;
for(int j = 1; j <= arr[i] && i + j < n; j++)
dp[i + j] = min(dp[i + j], dp[i] + 1);
}
cout << (dp[n-1] == INT_MAX ? -1 : dp[n-1]);
}
Output:
2
Java Implementation
import java.util.Arrays;
class Main {
public static void main(String[] args) {
int[] arr = {2,3,1,1,4};
int n = arr.length;
int[] dp = new int[n];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for(int i = 0; i < n; i++) {
if(dp[i] == Integer.MAX_VALUE || arr[i] == 0) continue;
for(int j = 1; j <= arr[i] && i + j < n; j++)
dp[i + j] = Math.min(dp[i + j], dp[i] + 1);
}
System.out.print(dp[n-1] == Integer.MAX_VALUE ? -1 : dp[n-1]);
}
}
Output:
2
Python Implementation
import sys
arr = [2,3,1,1,4]
n = len(arr)
dp = [sys.maxsize] * n
dp[0] = 0
for i in range(n):
if dp[i] == sys.maxsize or arr[i] == 0:
continue
for j in range(1, arr[i] + 1):
if i + j < n:
dp[i + j] = min(dp[i + j], dp[i] + 1)
print(-1 if dp[-1] == sys.maxsize else dp[-1])
Output:
2
C# Implementation
using System;
class Program {
static void Main() {
int[] arr = {2,3,1,1,4};
int n = arr.Length;
int[] dp = new int[n];
for(int i = 1; i < n; i++)
dp[i] = int.MaxValue;
for(int i = 0; i < n; i++) {
if(dp[i] == int.MaxValue || arr[i] == 0) continue;
for(int j = 1; j <= arr[i] && i + j < n; j++)
dp[i + j] = Math.Min(dp[i + j], dp[i] + 1);
}
Console.Write(dp[n - 1] == int.MaxValue ? -1 : dp[n - 1]);
}
}
Output:
2
Approach 3: Greedy (Optimal)
Idea
Track:
- maxReach → farthest index reachable
- steps → steps left in current jump
- jumps → number of jumps
Algorithm
- Initialize maxReach = arr[0], steps = arr[0], jumps = 1
- Traverse array
- Update max reach
- When steps become 0, take a jump
Time & Space Complexity
Time: O(n)
Space: O(1)
C++ Implementation
#include
using namespace std;
int main() {
int arr[] = {2,3,1,1,4};
int n = 5;
if(n <= 1) return 0;
if(arr[0] == 0) {
cout << -1;
return 0;
}
int jumps = 1, maxReach = arr[0], steps = arr[0];
for(int i = 1; i < n; i++) {
if(i == n - 1) {
cout << jumps;
return 0;
}
maxReach = max(maxReach, i + arr[i]);
steps--;
if(steps == 0) {
jumps++;
if(i >= maxReach) {
cout << -1;
return 0;
}
steps = maxReach - i;
}
}
cout << -1;
}
Output
2
Java Implementation
class Main {
public static void main(String[] args) {
int[] arr = {2,3,1,1,4};
int n = arr.length;
if(n <= 1) {
System.out.print(0);
return;
}
if(arr[0] == 0) {
System.out.print(-1);
return;
}
int jumps = 1, maxReach = arr[0], steps = arr[0];
for(int i = 1; i < n; i++) {
if(i == n - 1) {
System.out.print(jumps);
return;
}
maxReach = Math.max(maxReach, i + arr[i]);
steps--;
if(steps == 0) {
jumps++;
if(i >= maxReach) {
System.out.print(-1);
return;
}
steps = maxReach - i;
}
}
System.out.print(-1);
}
}
Output
2
Python Implementation
arr = [2,3,1,1,4]
n = len(arr)
if n <= 1:
print(0)
elif arr[0] == 0:
print(-1)
else:
jumps = 1
maxReach = arr[0]
steps = arr[0]
for i in range(1, n):
if i == n - 1:
print(jumps)
break
maxReach = max(maxReach, i + arr[i])
steps -= 1
if steps == 0:
jumps += 1
if i >= maxReach:
print(-1)
break
steps = maxReach - i
Output
2
C# Implementation
using System;
class Program {
static void Main() {
int[] arr = {2,3,1,1,4};
int n = arr.Length;
if(n <= 1) {
Console.Write(0);
return;
}
if(arr[0] == 0) {
Console.Write(-1);
return;
}
int jumps = 1, maxReach = arr[0], steps = arr[0];
for(int i = 1; i < n; i++) {
if(i == n - 1) {
Console.Write(jumps);
return;
}
maxReach = Math.Max(maxReach, i + arr[i]);
steps--;
if(steps == 0) {
jumps++;
if(i >= maxReach) {
Console.Write(-1);
return;
}
steps = maxReach - i;
}
}
Console.Write(-1);
}
}
Output
2
Summary
- Brute force is exponential and impractical
- DP improves but still slow for large inputs
- Greedy solution is optimal and interview-preferred
- Greedy solves the problem in a single pass
Next Problem in the Series
Chocolate Distribution Problem
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
