Linear time algorithm for Minimum number of jumps required to reach end

Question

Problem: Minimum number of jumps to reach end

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, then we cannot move through that element.

Example:

Input: arr[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9} Output: 3 (1-> 3 -> 8 ->9) First element is 1, so can only go to 3. Second element is 3, so can make at most 3 steps i.e. to 5 or 8 or 9.

Source: http://www.geeksforgeeks.org/minimum-number-of-jumps-to-reach-end-of-a-given-array/

I have made a linear time algorithm for finding Minimum number of jumps required to reach end of an array.

The source code is as below:

int minJumpsUpdated(int arr[], int n)
{
  int *jumps = malloc(n * sizeof(int));  // jumps[n-1] will hold the result
  int i =1, j = 0;

  jumps[0] = 0;
  for (i = 1; i < n; ) { 

    // if i is out of range of arr[j], then increment j
    if (arr[j] + j < i && j < i) {

      j++;

    // else if i is within range of arr[j], 
    //   jumps for ith element would be jumps[j]+1
    } else if (arr[j] + j >= i && j < i) {

      jumps[i] = jumps[j] + 1;
      i++;

    } else {
      printf("solution does not exist");
      return -1;
    }
  }

  printf("jumps: ");
  for (i = 0; i < n; i++) {
    printf("%d, ", jumps[i]);
  }
  return jumps[n - 1];
}

Example:

1.) initially i=1, j=0 and arr[] = {1, 3, 6, 1, 0, 9};

jumps[] = 0,0,0,0,0,0

2.) as i is within range of arr[j] ie. i<= j+arr[j], number of jumps required to go to ith position would be min number of jumps till jth position + 1.

i=2, j=0, jumps[] = 0,1,0,0,0,0

3.) i>j+arr[j] i.e. j++;

i=2, j=1, jumps[] = 0,1,0,0,0,0

4.) i<=j+arr[j] i.e. jumps[i] = jumps[j]+1;

i=3, j=1, jumps[] = 0,1,2,0,0,0

5.) i<=j+arr[j] i.e. jumps[i] = jumps[j]+1;

i=4, j=1, jumps[] = 0,1,2,2,0,0

6.) i<=j+arr[j] i.e. jumps[i] = jumps[j]+1;

i=5, j=1, jumps[] = 0,1,2,2,2,0

7.) i>j+arr[j] i.e. j++;

i=5, j=2, jumps[] = 0,1,2,2,2,0

8.) i<=j+arr[j] i.e. jumps[i] = jumps[j]+1;

i=6, j=2, jumps[] = 0,1,2,2,2,3

------ END ------

I am not able to figure out under which test case this program will not work. I am asking this because on internet the optimized solution is using DP which is O(n^2). My solution is linear time. i.e. O(n). So I am assuming there are some cases which this algorithm will not handle. So I am curious what cases it does not handle.

Your help will be appreciated.

Thank you.

Answer 1

Summary of your algorithm:

1. Take the first item and look how far you can get with this
   (incrementing i until arr[j]+j < i)
2. Go to the next item that you can reach from the first one and that takes you at least to ith item.
3. Repeat this until you reach the last entry.

First:
Yes it runs in O(n) since the algorithm pushes both i an j only one time from 1 to n in worst case.

Second
I have not seen a proof that O(n²) is the optimal time-complexity.

Thrid
You can visualize the arr like this so this is exactly what your algorithm does. You can use this to proof by induction that your algorithm is correct. But as @Leo mentioned, there has to be a solution.

Fix for no-solution-case
Make sure that j < i holds.