Minimum number of jumps to reach the end of an array

Given an array with positive integers, we need to find the minimum number of jumps it takes to reach end of the array from start of the array.

Note: Here, you can jump as many steps from the particular point as the value at that point.

For Example : [2, 3, 1, 1, 2, 4, 2]

Here, from index 0 I can jump to index 1 and 2 because the value here is 2, here second element is 3 we can make at most 3 jumps, example to 1 or second 1 or 2.

Example

Input array : [2, 3, 1, 1, 2, 4, 7]

Output : 3

Here, 2 → 3 → 2 → 7 it takes 3 jumps. If we do 2 → 1 → 1 → 2 → 7 it takes 4 jumps. So, we don’t jump to 1 from 2 even though we travel 2 steps.

Method 1

Time complexity : O(n2)

Algorithm

Here, we use recursive approach, starting from first element for all elements reachable from first element we call the function again recurseively.
MinJumps(Start, End) = Min(MinJumps(K, end)), for all K reachable from start.
We use this idea,

  1. If source and destination are same. Jumps = 0
  2. If element is equal to zero, we cannot reach the end. So, print INT_MAX.
  3. Traverse through all the points reachable from start. Recursively get minimum number of jumps needed  to reach end from these points.
  4. Return minimum number of jumps finally.

C++ Program

#include <stdio.h>
#include <limits.h>
#include <bits/stdc++.h>

using namespace std;
  
// Returns minimum number of NumOfJumps to reach arr[high] from arr[low]
int MinJumps(int arr[], int low, int high)
{
   if (high == low)//source and destination are same.
   {
     return 0;
   }
   if (arr[low] == 0)//cannot move forward,
   {
     return INT_MAX;
   }
   int MinNumOfJumps = INT_MAX;//initialize to INT_MAX
  
   //Recursively calling for all reacheble points. 
   for (int i = low+1; i<= high && i <= low + arr[low]; i++)
   {
       int NumOfJumps = MinJumps(arr, i, high);
       if(NumOfJumps != INT_MAX && NumOfJumps + 1 < MinNumOfJumps)
       {
           MinNumOfJumps = NumOfJumps + 1;
       }
   }
   return MinNumOfJumps;
}
 
//Main function
int main()
{
  int input_array[] = {1,4,3,7,1,2,6,7,6};
  int N = sizeof(input_array)/sizeof(input_array[0]);
  cout<<"Minimum number of jumps to reach the end is eqaul to: "<<MinJumps(input_array, 0, N-1);
  return 0;
}
Try It
 

Method 2

Time complexity: O(n2)

Algorithm

In this method, we use Dynamic programming,

  1. We create a jumps[] array, where jumps[i] indicates the minimum number of jumps needed to reach array[i] from array[0].
  2. Jumps[N-1] will be the minimum number of jumps to reach the end from start of the given input array.
  3. In the jumps array, we initialize the array with first element equal to zero and rest elements equal to infinite(INT_MAX).
  4. We keep updating the jump array till last element by the condition,

If ( i <= j + array[j]) → jumps[i] = min(jumps(i), jumps(j) + 1) here we are just comparing the number of jumps from all the reachable points with itself.

Algorithm Working

C++ Program

#include <stdio.h>
#include <limits.h>
#include <bits/stdc++.h>

using namespace std;
  
// Returns minimum number of NumOfJumps to reach end from start
int MinJumps(int array[], int N)
{
    int *jumps_array = new int[N];
    if (N == 0 || array[0] == 0)
    {
        return INT_MAX;
    }
    jumps_array[0] = 0;//initializing jumps_array
    for (int i = 1; i < N; ++i)
    {
        jumps_array[i] = INT_MAX;
    }
    for (int i = 1; i < N; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (i <= j + array[j] && jumps_array[j] != INT_MAX)//minimum number jumps to reach i 
            {
                 jumps_array[i] = min(jumps_array[i], jumps_array[j] + 1);//by comparing with previous points
                 break;
            }
        }
    }
    return jumps_array[N-1];
}
int min(int x, int y)
{
    if(x < y)
    {
        return x;
    }
    else
    {
        return y;
    }   
}
//Main function
int main()
{
    int input_array[] = {1,4,3,7,1,2,6,7,6};
    int N = sizeof(input_array)/sizeof(input_array[0]);
    cout<<"Minimum number of jumps to reach the end is eqaul to: "<<MinJumps(input_array,N); 
    return 0;
}
Try It


Next > < Prev
Scroll to Top