Question: Given an array, start from the first element and reach the last by jumping. The jump length can be at most the value at the current position in the array. Optimum result is when you reach the goal in minimum number of jumps.

Example:

Given array A = {2,3,1,1,4}

Possible ways to reach the end (index list)

  1. 0,2,3,4 (jump 2 to index 2, and then jump 1 to index 3 and then jump 1 to index 4)
  2. 0,1,4 (jump 1 to index 1, and then jump 3 to index 4)
Since second solution has only 2 jumps it is the optimum result.

Answer: This problem is a classic example of Dynamic Programming. Though we can solve this by brute-force but complexity in that case will be horrendous. If you remember LIS problem or my first post on dynamic programming then we can solve this by using same process.

As soon as we traverse the array, we should find the minimum number of jumps for reaching that position (index) and update our result array. Once we reach at the end, we have the optimum solution at last index in result array.

How to find optimum number of jump for every position (index)?

For first index, optimum number of jumps will be zero. Please note that if value at first index is zero, we can’t jump to any element and return infinite.

For (N+1)th element, initialize result[N+1] as infinite. Then we should go through a loop from 0…N, and at every index (i), we should see if we are able to jump to (N+1) from there (i) or not. If possible then see if total number of jump (result[i] + 1) is less than result[N+1], then update result[N+1] else just continue to next index.

Code: I skipped algorithm but commented code properly. 


//Define MAX 1 less so that adding 1 doesn't make it 0
#define MAX 0xFFFFFFFE;

unsigned int jump(int *array, int n)
{
  unsigned int
*result = new unsigned int[n];
  int i, j;
  
  //Boundry conditions
  if (n==0 || array[0] == 0)
    return MAX;
    
  result[0] = 0;  //no need to jump at first element
  for (i = 1; i < n; i++)
  {
    result[i] = MAX; //Initialization of result[i]
    for (j = 0; j < i; j++)
    {
      //check if jump is possible from j to is
      if (array[j] >= (i-j))      {

        //check if better solution available
        if ((result[j] + 1) < result[i]) 
          result[i] = result[j] + 1;  //updating result[i]
      }
    }
  }
  
  //return result[n-1]
  unsigned int answer = result[n-1];
  delete[] result;
  
  return answer;
}


Above code will return optimum number of jumps only. If we want to have the jump indexes as well, we can very easily modify the code as per requirement.

Efficiency: Since we are running 2 loops here and iterating from 0 to I in every loop then total time takes will be 1 + 2 + 3 + 4 + … + (N-1).

So time efficiency O(n) = O(n*(n-1)/2) = O(n^2)

We also need O(n) space for result array.

Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.