Given an array arr[] where each element represents the max number of steps that can be made forward from that index. The task is to find the minimum number of jumps to reach the end of the array starting from index 0.
Examples:
Input: arr[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}
Output: 3 (1-> 3 -> 9 -> 9)
Explanation: Jump from 1st element to 2nd element as there is only 1 step.
Now there are three options 5, 8 or 9. If 8 or 9 is chosen then the end node 9 can be reached. So 3 jumps are made.Input: arr[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
Output: 10
Explanation: In every step a jump is needed so the count of jumps is 10.
Minimum number of jumps to reach the end using Recursion:
Start from the first element and recursively call for all the elements reachable from the first element. The minimum number of jumps to reach end from first can be calculated using the minimum value from the recursive calls.
minJumps(start, end) = 1 + Min(minJumps(k, end)) for all k reachable from start.
Follow the steps mentioned below to implement the idea:
- Create a recursive function.
- In each recursive call get all the reachable nodes from that index.
- For each of the index call the recursive function.
- Find the minimum number of jumps to reach the end from current index.
- Return the minimum number of jumps from the recursive call.
Below is the Implementation of the above approach:
C++
// C++ program to find Minimum // number of jumps to reach end #include <bits/stdc++.h> using namespace std; // Function to return the minimum number // of jumps to reach arr[h] from arr[l] int minJumps(int arr[], int l,int h) { // Base case: when source and destination are same if (h == l) return 0; // When nothing is reachable from the given source if (arr[l] == 0) return INT_MAX; // Traverse through all the points // reachable from arr[l] // Recursively, get the minimum number // of jumps needed to reach arr[h] from // these reachable points int min = INT_MAX; for (int i = l + 1; i <= h && i <= l + arr[l]; i++) { int jumps = minJumps(arr, i, h); if (jumps != INT_MAX && jumps + 1 < min) min = jumps + 1; } return min; } // Driver Code int main() { int arr[] = { 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9 }; int n = sizeof(arr) / sizeof(arr[0]); cout << "Minimum number of jumps to"; cout << " reach the end is " << minJumps(arr, 0,n-1); return 0; } // This code is contributed // by Shivi_Aggarwal |
C
// C program to find Minimum // number of jumps to reach end #include <limits.h> #include <stdio.h> // Returns minimum number of // jumps to reach arr[h] from arr[l] int minJumps(int arr[], int l, int h) { // Base case: when source and destination are same if (h == l) return 0; // When nothing is reachable from the given source if (arr[l] == 0) return INT_MAX; // Traverse through all the points // reachable from arr[l]. Recursively // get the minimum number of jumps // needed to reach arr[h] from these // reachable points. int min = INT_MAX; for (int i = l + 1; i <= h && i <= l + arr[l]; i++) { int jumps = minJumps(arr, i, h); if (jumps != INT_MAX && jumps + 1 < min) min = jumps + 1; } return min; } // Driver program to test above function int main() { int arr[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9 }; int n = sizeof(arr) / sizeof(arr[0]); printf("Minimum number of jumps to reach end is %d ", minJumps(arr, 0, n - 1)); return 0; } |
Java
// Java program to find Minimum // number of jumps to reach end import java.io.*; import java.util.*; class GFG { // Returns minimum number of // jumps to reach arr[h] from arr[l] static int minJumps(int arr[], int l, int h) { // Base case: when source // and destination are same if (h == l) return 0; // When nothing is reachable // from the given source if (arr[l] == 0) return Integer.MAX_VALUE; // Traverse through all the points // reachable from arr[l]. Recursively // get the minimum number of jumps // needed to reach arr[h] from these // reachable points. int min = Integer.MAX_VALUE; for (int i = l + 1; i <= h && i <= l + arr[l]; i++) { int jumps = minJumps(arr, i, h); if (jumps != Integer.MAX_VALUE && jumps + 1 < min) min = jumps + 1; } return min; } // Driver code public static void main(String args[]) { int arr[] = { 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9 }; int n = arr.length; System.out.print( "Minimum number of jumps to reach end is " + minJumps(arr, 0, n - 1)); } } // This code is contributed by Sahil_Bansall |
Python3
# Python3 program to find Minimum # number of jumps to reach end # Returns minimum number of jumps # to reach arr[h] from arr[l] def minJumps(arr, l, h): # Base case: when source and # destination are same if (h == l): return 0 # when nothing is reachable # from the given source if (arr[l] == 0): return float('inf') # Traverse through all the points # reachable from arr[l]. Recursively # get the minimum number of jumps # needed to reach arr[h] from # these reachable points. min = float('inf') for i in range(l + 1, h + 1): if (i < l + arr[l] + 1): jumps = minJumps(arr, i, h) if (jumps != float('inf') and jumps + 1 < min): min = jumps + 1 return min # Driver program to test above function arr = [1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9] n = len(arr) print('Minimum number of jumps to reach', 'end is', minJumps(arr, 0, n-1)) # This code is contributed by Soumen Ghosh |
C#
// C# program to find Minimum // number of jumps to reach end using System; class GFG { // Returns minimum number of // jumps to reach arr[h] from arr[l] static int minJumps(int[] arr, int l, int h) { // Base case: when source // and destination are same if (h == l) return 0; // When nothing is reachable // from the given source if (arr[l] == 0) return int.MaxValue; // Traverse through all the points // reachable from arr[l]. Recursively // get the minimum number of jumps // needed to reach arr[h] from these // reachable points. int min = int.MaxValue; for (int i = l + 1; i <= h && i <= l + arr[l]; i++) { int jumps = minJumps(arr, i, h); if (jumps != int.MaxValue && jumps + 1 < min) min = jumps + 1; } return min; } // Driver code public static void Main() { int[] arr = { 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9 }; int n = arr.Length; Console.Write( "Minimum number of jumps to reach end is " + minJumps(arr, 0, n - 1)); } } // This code is contributed by Sam007 |
Javascript
<script> // JavaScript program to find Minimum // number of jumps to reach end // Function to return the minimum number // of jumps to reach arr[h] from arr[l] function minJumps(arr, n) { // Base case: when source and // destination are same if (n == 1) return 0; // Traverse through all the points // reachable from arr[l] // Recursively, get the minimum number // of jumps needed to reach arr[h] from // these reachable points let res = Number.MAX_VALUE; for (let i = n - 2; i >= 0; i--) { if (i + arr[i] >= n - 1) { let sub_res = minJumps(arr, i + 1); if (sub_res != Number.MAX_VALUE) res = Math.min(res, sub_res + 1); } } return res; } // Driver Code let arr = [ 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9 ]; let n = arr.length; document.write("Minimum number of jumps to"); document.write(" reach end is " + minJumps(arr, n)); </script> |
PHP
<?php // php program to find Minimum // number of jumps to reach end // Returns minimum number of jumps // to reach arr[h] from arr[l] function minJumps($arr, $l, $h) { // Base case: when source and // destination are same if ($h == $l) return 0; // When nothing is reachable // from the given source if ($arr[$l] == 0) return $h+1; // Traverse through all the points // reachable from arr[l]. Recursively // get the minimum number of jumps // needed to reach arr[h] from these // reachable points. $min = 999999; for ($i = $l+1; $i <= $h && $i <= $l + $arr[$l]; $i++) { $jumps = minJumps($arr, $i, $h); if($jumps != 999999 && $jumps + 1 < $min) $min = $jumps + 1; } return $min; } // Driver program to test above function $arr = array(1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9); $n = count($arr); echo "Minimum number of jumps to reach " . "end is ". minJumps($arr, 0, $n-1); // This code is contributed by Sam007 ?> |
Output
Minimum number of jumps to reach the end is 3
Time complexity: O(nn). There are maximum n possible ways to move from an element. So the maximum number of steps can be nn.
Auxiliary Space: O(n). For recursion call stack.
Minimum number of jumps to reach the end Using Dynamic Programming (Memoization):
It can be observed that there will be overlapping subproblems.
For example in array, arr[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9} minJumps(3, 9) will be called two times as arr[3] is reachable from arr[1] and arr[2]. So this problem has both properties (optimal substructure and overlapping subproblems) of Dynamic Programming.
Follow the below steps to implement the idea:
- Create memo[] such that memo[i] indicates the minimum number of jumps needed to reach memo[n-1] from memo[i] to store previously solved subproblems.
- During the recursion call, if the same state is called more than once, then we can directly return the answer stored for that state instead of calculating again.
- Otherwise, In each recursive call get all the reachable nodes from that index.
- For each of the index call the recursive function.
- Find the minimum number of jumps to reach the end from current index.
C++
#include <bits/stdc++.h> using namespace std; int jump(vector<int>& nums, int idx, int end, vector<int>& memo) { //we reached the end. No jumps to make further if (idx == end) return 0; if (memo[idx] != -1) return memo[idx]; int min_jumps = INT_MAX - 1; //we will try to make all possible jumps from current index //and select the minimum of those //It does not matter if we try from 1 to nums[idx] //or from nums[idx] to 1 for (int j = nums[idx]; j >= 1; --j) { //If we make this jump 'j' distance away from idx //do we overshoot? //if we land within the nums, we will test further if (idx + j <= end) { //Make a jump to idx + j index and explore further //then update min_jumps with the minimum jumps //we made to reach end while trying all possible //nums[idx] jumps from current index. min_jumps = std::min(min_jumps, 1 + jump(nums, idx + j, end, memo)); } } return memo[idx] = min_jumps; } //Memoization int minJumps(vector<int>& nums) { vector<int> memo(nums.size(), -1); return jump(nums, 0, nums.size() - 1, memo); } int main() { int n = 11; vector<int> arr{ 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9 }; cout << minJumps(arr) << endl; return 0; } // This code is contributed by Tushar Seth |
Java
import java.util.Arrays; public class Geek { // Helper function to find the minimum jumps required to reach the end private static int jump(int[] nums, int idx, int end, int[] memo) { // We reached the end. No jumps to make further if (idx == end) return 0; if (memo[idx] != -1) return memo[idx]; int min_jumps = Integer.MAX_VALUE - 1; // We will try to make all possible jumps from the current index // and select the minimum of those. // It does not matter if we try from 1 to nums[idx] or from nums[idx] to 1. for (int j = nums[idx]; j >= 1; --j) { // If we make this jump 'j' distance away from idx, // do we overshoot? // If we land within the nums, we will test further. if (idx + j <= end) { // Make a jump to idx + j index and explore further, // then update min_jumps with the minimum jumps // we made to reach the end while trying all possible // nums[idx] jumps from the current index. min_jumps = Math.min(min_jumps, 1 + jump(nums, idx + j, end, memo)); } } return memo[idx] = min_jumps; } // Memoization private static int minJumps(int[] nums) { int[] memo = new int[nums.length]; Arrays.fill(memo, -1); return jump(nums, 0, nums.length - 1, memo); } public static void main(String[] args) { int[] arr = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}; System.out.println(minJumps(arr)); } } |
Python3
# Helper function to find the minimum jumps required to reach the end def jump(nums, idx, end, memo): # We reached the end. No jumps to make further if idx == end: return 0 if memo[idx] != -1: return memo[idx] min_jumps = float("inf") # We will try to make all possible jumps from the current index # and select the minimum of those. # It does not matter if we try from 1 to nums[idx] or from nums[idx] to 1. for j in range(nums[idx], 0, -1): # If we make this jump 'j' distance away from idx, # do we overshoot? # If we land within the nums, we will test further. if idx + j <= end: # Make a jump to idx + j index and explore further, # then update min_jumps with the minimum jumps # we made to reach the end while trying all possible # nums[idx] jumps from the current index. min_jumps = min(min_jumps, 1 + jump(nums, idx + j, end, memo)) memo[idx] = min_jumps return memo[idx] def min_jumps(nums): """Memoization""" memo = [-1 for i in range(len(nums))] jump(nums, 0, len(nums) - 1, memo) return memo[0] if __name__ == "__main__": arr = [1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9] print(min_jumps(arr)) # this code is contributed by Rohit Singh |
C#
using System; class JumpGame { // Recursive function to find minimum jumps required to // reach the end static int Jump(int[] nums, int idx, int end, int[] memo) { // We reached the end, no more jumps needed if (idx == end) return 0; // If memoization contains a value, return it if (memo[idx] != -1) return memo[idx]; int minJumps = int.MaxValue - 1; // Try all possible jumps from the current index for (int j = nums[idx]; j >= 1; j--) { // Check if making the jump 'j' distance away // from idx overshoots the end if (idx + j <= end) { // Make the jump to idx + j index and // explore further Update minJumps with the // minimum jumps to reach the end minJumps = Math.Min( minJumps, 1 + Jump(nums, idx + j, end, memo)); } } // Memoize the result and return it return memo[idx] = minJumps; } // Memoization function to find minimum jumps static int MinJumps(int[] nums) { int[] memo = new int[nums.Length]; Array.Fill(memo, -1); return Jump(nums, 0, nums.Length - 1, memo); } static void Main() { int[] arr = { 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9 }; Console.WriteLine(MinJumps(arr)); } } |
Javascript
function jump(nums, idx, end, memo) { // We reached the end. No jumps to make further. if (idx === end) return 0; if (memo[idx] !== -1) return memo[idx]; let min_jumps = Number.MAX_SAFE_INTEGER - 1; // We will try to make all possible jumps from the current index // and select the minimum of those. // It does not matter if we try from 1 to nums[idx] or from nums[idx] to 1. for (let j = nums[idx]; j >= 1; --j) { // If we make this jump 'j' distance away from idx, // do we overshoot? // If we land within the nums, we will test further. if (idx + j <= end) { // Make a jump to idx + j index and explore further, // then update min_jumps with the minimum jumps // we made to reach the end while trying all possible // nums[idx] jumps from the current index. min_jumps = Math.min(min_jumps, 1 + jump(nums, idx + j, end, memo)); } } return memo[idx] = min_jumps; } function minJumps(nums) { const memo = Array(nums.length).fill(-1); return jump(nums, 0, nums.length - 1, memo); } const arr = [1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9]; console.log(minJumps(arr)); |
Output
3
Time complexity: O(n^2) as for each position i the recursive function is called once and a loop runs for O(n) for each position in the worst case denoting the number of reachable positions from position i.
Auxiliary Space: O(n), because of recursive stack space and memo array.
Minimum number of jumps to reach the end using Dynamic Programming (Tabulation):
Follow the below steps to implement the idea:
- Create jumps[] array from left to right such that jumps[i] indicate the minimum number of jumps needed to reach arr[i] from arr[0].
- To fill the jumps array run a nested loop inner loop counter is j and the outer loop count is i.
- Outer loop from 1 to n-1 and inner loop from 0 to i.
- If i is less than j + arr[j] then set jumps[i] to minimum of jumps[i] and jumps[j] + 1. initially set jump[i] to INT MAX
- Return jumps[n-1].
Below is the implementation of the above approach:
C++
// C++ program for Minimum number // of jumps to reach end #include <bits/stdc++.h> using namespace std; int min(int x, int y) { return (x < y) ? x : y; } // Returns minimum number of jumps // to reach arr[n-1] from arr[0] int minJumps(int arr[], int n) { // jumps[n-1] will hold the result int* jumps = new int[n]; int i, j; if (n == 0 || arr[0] == 0) return INT_MAX; jumps[0] = 0; // Find the minimum number of jumps to reach arr[i] // from arr[0], and assign this value to jumps[i] for (i = 1; i < n; i++) { jumps[i] = INT_MAX; for (j = 0; j < i; j++) { if (i <= j + arr[j] && jumps[j] != INT_MAX) { jumps[i] = min(jumps[i], jumps[j] + 1); break; } } } return jumps[n - 1]; } // Driver code int main() { int arr[] = { 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9 }; int size = sizeof(arr) / sizeof(int); cout << "Minimum number of jumps to reach end is " << minJumps(arr, size); return 0; } // This is code is contributed by rathbhupendra |
C
// C program for Minimum number // of jumps to reach end #include <limits.h> #include <stdio.h> int min(int x, int y) { return (x < y) ? x : y; } // Returns minimum number of // jumps to reach arr[n-1] from arr[0] int minJumps(int arr[], int n) { // jumps[n-1] will hold the result int jumps[n]; int i, j; if (n == 0 || arr[0] == 0) return INT_MAX; jumps[0] = 0; // Find the minimum number of // jumps to reach arr[i] // from arr[0], and assign this // value to jumps[i] for (i = 1; i < n; i++) { jumps[i] = INT_MAX; for (j = 0; j < i; j++) { if (i <= j + arr[j] && jumps[j] != INT_MAX) { jumps[i] = min(jumps[i], jumps[j] + 1); break; } } } return jumps[n - 1]; } // Driver program to test above function int main() { int arr[] = { 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9 }; int size = sizeof(arr) / sizeof(int); printf("Minimum number of jumps to reach end is %d ", minJumps(arr, size)); return 0; } |
Java
// JAVA Code for Minimum number // of jumps to reach end import java.io.*; class GFG { private static int minJumps(int[] arr, int n) { // jumps[n-1] will hold the int jumps[] = new int[n]; // result int i, j; // if first element is 0, if (n == 0 || arr[0] == 0) return Integer.MAX_VALUE; // end cannot be reached jumps[0] = 0; // Find the minimum number of jumps to reach arr[i] // from arr[0], and assign this value to jumps[i] for (i = 1; i < n; i++) { jumps[i] = Integer.MAX_VALUE; for (j = 0; j < i; j++) { if (i <= j + arr[j] && jumps[j] != Integer.MAX_VALUE) { jumps[i] = Math.min(jumps[i], jumps[j] + 1); break; } } } return jumps[n - 1]; } // driver program to test above function public static void main(String[] args) { int arr[] = { 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9 }; System.out.println( "Minimum number of jumps to reach end is : " + minJumps(arr, arr.length)); } } // This code is contributed by Arnav Kr. Mandal. |
Python3
# Python3 program to find Minimum # number of jumps to reach end # Returns minimum number of jumps # to reach arr[n-1] from arr[0] def minJumps(arr, n): jumps = [0 for i in range(n)] if (n == 0) or (arr[0] == 0): return float('inf') jumps[0] = 0 # Find the minimum number of # jumps to reach arr[i] from # arr[0] and assign this # value to jumps[i] for i in range(1, n): jumps[i] = float('inf') for j in range(i): if (i <= j + arr[j]) and (jumps[j] != float('inf')): jumps[i] = min(jumps[i], jumps[j] + 1) break return jumps[n-1] # Driver Program to test above function arr = [1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9] size = len(arr) print('Minimum number of jumps to reach', 'end is', minJumps(arr, size)) # This code is contributed by Soumen Ghosh |
C#
// C# Code for Minimum number of jumps to reach end using System; class GFG { static int minJumps(int[] arr, int n) { // jumps[n-1] will hold the // result int[] jumps = new int[n]; // if first element is 0, if (n == 0 || arr[0] == 0) // end cannot be reached return int.MaxValue; jumps[0] = 0; // Find the minimum number of // jumps to reach arr[i] // from arr[0], and assign // this value to jumps[i] for (int i = 1; i < n; i++) { jumps[i] = int.MaxValue; for (int j = 0; j < i; j++) { if (i <= j + arr[j] && jumps[j] != int.MaxValue) { jumps[i] = Math.Min(jumps[i], jumps[j] + 1); break; } } } return jumps[n - 1]; } // Driver program public static void Main() { int[] arr = { 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9 }; Console.Write( "Minimum number of jumps to reach end is : " + minJumps(arr, arr.Length)); } } // This code is contributed by Sam007 |
Javascript
<script> // JavaScript Code for Minimum number // of jumps to reach end function minJumps(arr , n) { // jumps[n-1] will hold the var jumps = Array.from({length: n}, (_, i) => 0);; // result var i, j; // if first element is 0, if (n == 0 || arr[0] == 0) return Number.MAX_VALUE; // end cannot be reached jumps[0] = 0; // Find the minimum number of jumps to reach arr[i] // from arr[0], and assign this value to jumps[i] for (i = 1; i < n; i++) { jumps[i] = Number.MAX_VALUE; for (j = 0; j < i; j++) { if (i <= j + arr[j] && jumps[j] != Number.MAX_VALUE) { jumps[i] = Math.min(jumps[i], jumps[j] + 1); break; } } } return jumps[n - 1]; } // driver program to test above function var arr = [ 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9 ]; document.write("Minimum number of jumps to reach end is : " + minJumps(arr, arr.length)); // This code contributed by shikhasingrajput </script> |
PHP
<?php // PHP code for Minimum number of // jumps to reach end // Returns minimum number of jumps // to reach arr[n-1] from arr[0] function minJumps($arr, $n) { // jumps[n-1] will // hold the result $jumps = array($n); if ($n == 0 || $arr[0] == 0) return 999999; $jumps[0] = 0; // Find the minimum number of // jumps to reach arr[i] // from arr[0], and assign // this value to jumps[i] for ($i = 1; $i < $n; $i++) { $jumps[$i] = 999999; for ($j = 0; $j < $i; $j++) { if ($i <= $j + $arr[$j] && $jumps[$j] != 999999) { $jumps[$i] = min($jumps[$i], $jumps[$j] + 1); break; } } } return $jumps[$n-1]; } // Driver Code $arr = array(1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9); $size = count($arr); echo "Minimum number of jumps to reach end is ". minJumps($arr, $size); // This code is contributed by Sam007 ?> |
Output
Minimum number of jumps to reach end is 3
Time Complexity: O(n2)
Auxiliary Space: O(n), since n extra space has been taken.
Refer to the article given below to solve this problem in O(n) time:
Minimum number of jumps to reach end | Set 2 (O(n) solution)
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
