Minimum number of jumps to reach end

Software Development
#1

Hello Everyone,

Given an array of integers where each element represents the max number of steps that can be made forward from that element. Write a function to return the minimum number of jumps to reach the end of the array (starting from the first element). If an element is 0, they cannot move through that element. If the end isn’t reachable, return -1.

Examples:

Input: arr[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9} Output: 3 (1-> 3 → 8 → 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.

The first element is 1, so can only go to 3. The second element is 3, so can make at most 3 steps eg to 5 or 8 or 9.

Method 1: Naive Recursive Approach.
Approach: A naive approach is to start from the first element and recursively call for all the elements reachable from first element. The minimum number of jumps to reach end from first can be calculated using minimum number of jumps needed to reach end from the elements reachable from first.

minJumps(start, end) = Min ( minJumps(k, end) ) for all k reachable from start

// 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 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

int res = INT_MAX;

for ( int i = n - 2; i >= 0; i--) {

if (i + arr[i] >= n - 1) {

int sub_res = minJumps(arr, i + 1);

if (sub_res != INT_MAX)

res = min(res, sub_res + 1);

}

}

return res;

}

// Driver Code

int main()

{

int arr[] = { 1, 3, 6, 3, 2,

3, 6, 8, 9, 5 };

int n = sizeof (arr) / sizeof (arr[0]);

cout << "Minimum number of jumps to" ;

cout << " reach the end is " << minJumps(arr, n);

return 0;

}

Output:

Minimum number of jumps to reach end is 4

Complexity Analysis:

  • Time complexity: O(n^n).
    There are maximum n possible ways to move from a element. So maximum number of steps can be N^N so the upperbound of time complexity is O(n^n)
  • Auxiliary Space: O(1).
    There is no space required (if recursive stack space is ignored).

Note: If the execution is traced for this method, it can be seen that there will be overlapping subproblems. For example, 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.

Method 2: Dynamic Programming.
Approach:

  1. In this way, make a jumps[] array from left to right such that jumps[i] indicate the minimum number of jumps needed to reach arr[i] from arr[0].
  2. To fill the jumps array run a nested loop inner loop counter is j and outer loop count is i.
  3. Outer loop from 1 to n-1 and inner loop from 0 to n-1.
  4. 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
  5. Finally, return jumps[n-1].

// 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, 6, 1, 0, 9 };

int size = sizeof (arr) / sizeof ( int );

cout << "Minimum number of jumps to reach end is "

<< minJumps(arr, size);

return 0;

}

Output:

Minimum number of jumps to reach end is 3

Time Complexity: O(n^2)