What is the minimum number of jumps in an array?

We're given an array in which each element represents the maximum number of steps that can be taken from that element. We want to make a function that returns the minimum number of steps required to reach the end of the array from the first index of the array.

Examples

Some of the examples of this problem are as follows:

Example 1

Input array: $\{1, 1, 1, 1, 1, 1, 1\}$

Output: Minimum of 6 Jumps are required to reach the end.

Example 2

Input array: $\{1, 0, 1, 1, 1\}$

Output array: We cannot reach the end of this array.

Example 3

Input array: $\{1, 3, 1, 2, 4, 5, 8, 2, 1\}$

Output array: Minimum 3 Jumps are required to reach the end.

Code

The C++ code for this problem is as follows:

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int minimumJumps(int arr[], int len) {
  int* jumpArray = new int[len];
  jumpArray[0] = 0; // We need 0 steps to reach the first index of the array.
  for (int i = 1; i < len; i++) {
          // initializing with maximum number, thus if we 
          // cannot reach the end of array this function 
          // will return the end of array.
          jumpArray[i] = INT_MAX; 
          for (int j = 0; j < i; j++) {
              if (i <= (j + arr[j]) && jumpArray[j] != INT_MAX) {
                  if(jumpArray[j] + 1 < jumpArray[i])
                      jumpArray[i] = jumpArray[j] + 1;
                  break;
              }
          }
      }
  return jumpArray[len - 1];
}
int main() {
  int inp_arr[] = {1, 1, 1, 1, 0, 9};
  int length = sizeof(inp_arr)/sizeof(inp_arr[0]);
  if(length == 0) {
    cout << "The array is empty. Please add some values and try again.";
    return 0;
  }
  int answer = minimumJumps(inp_arr, length);
  if(answer > length) {
    cout << "We cannot reach the end of this array.";
  }
  else {
    cout << "Minimum jumps needed to reach the end of the array are ";
    cout << answer;
  }
  return 0;
}

Explanation

The most efficient way to solve this problem is dynamic programming. However, we can also solve it by using other methods.

We approach this problem in the following order:

We make a jumpArray (of the size of the original array) from left to right. Every element i in this array jumpArray[i] represents the minimum number of jumps needed to reach arr[i] from arr[0].
We make a nested loop in which the outer loop iterates over the entire array and the inner loop starts from index 0 and ends at the current index of the outer array.
If $i$ is less than j + arr[j] then we check for the minimum value between jumpsArray[i] and jumpsArray[j] + 1 in line 13. Then we set jumps[i] to the minimum of these two values.
Our final result is in the last index of jumpArray.
Thus, we return jumpArray[len - 1].

Time complexity

We are looping over the entire array two times in the nested loop. Thus, the time complexity of this algorithm is $O(N^2).$

Space complexity

We are making a jump array (named jumpArray in the above code) which is of the same length as the input array thus, the space complexity of this algorithm is $O(N).$

Free AI Mock Interviews

Coding Interview

Coding PatternsFree Interview

Gain insights and practical experience with coding patterns through targeted MCQs and coding problems, designed to match and challenge your expertise level.

System Design

You TubeFree Interview

Learn to design a video streaming platform like YouTube by tackling functional and non-functional requirements, core components, and high-level to detailed design challenges.

Free Resources