Minimum number of jumps to reach end of array

Minimum number of jumps to reach end of array

Given an array of integers, you can maximum jump a[i] positions from given index i. Find minimum number of jumps to reach end of array. For example, in following array, minimum number of jumps is 2.

minimum number of jumps to reach end

minimum jumps to reach at end of array

At 2 we can either jump 0, 1 or 2 indices at a time. If we jump 2 indices, we would require two more jumps (at 1 and 1) to reach at 4.
However if we jump only one index, next time we will reach at the end of the array

Minimum number of jumps to reach end

While finding minimum number of jumps to reach at end of array, something has to be minimized, that something is jumps. How can we do that?

Brute force way to solve this is to take longest jump possible from each index. While taking jump, take care that which among the possible landing indexes can give us maximum jump ahead. With every jump, select an index which gives maximum jump from that index. Just greedy algorithm at play.
Mathematically, for index i, scan through all indices e from i+1 till e = i + a[i] and calculate a value v = e +a[e]. Take e with maximum v. Let’s work out an example:

For example, in above array, for i =0, e = 1 and v = 1 (e)+3 (a[e]) =4;
e = 2 and v = 2 + 1 = 3
Select e which gives maximum v, that is 1. Once e is selected, i becomes that selected e. i = 1. A[i] = 3.

Since i + A[i] reaches at the end, we do not need to check anything else and break. Minimum number of jumps required to reach at the end of array is 2.

#include<stdio.h>
#define INFINITY 9999
 
int minimumJumps(int a[], int size){
 
    int max=0,count=0;
 
    for(int i=0; i<size; ){
        count++;
        max = 0;
        for(int j =0; j< a[i]; j++){
            if(max < j+a[i+j]){
                max = j + a[i+j];
            }
        }
        if(max == 0) return INFINITY;
 
        i = i+max;
    }
    return count;
}
//driver program
int main(){
    int a[] = {1,1,2,3,1,4};
    int size = sizeof(a)/sizeof(a[0]);
    printf("Minimum Jump : %d", minimumJumps(a, size));
    return 0;
}

What will be complexity of this method to find minimum number of jumps to reach end? It would be O(N2).

Minimum number of jumps to reach end : Dynamic programming

Can we solve this using dynamic programming?  What’s needed is to find minimum jumps to reach Nth index. We can reduce this problem like,

If we find minimum number of jumps for 0 and N-1 and can reach from any of them to Nth item, jumps for Nth index would be one more than that.

Declare an distance array which will store minimum number of jumps to reach each index of array. Distance[i] will store minimum jumps to reach at index i. Distance[0] =0 as nothing is required to reach index 0. Distance[N] is what we are looking for.

If we cannot jump from index o to any index in array, we just return infinity as result. If that is not the case, proceed further and initialize number of jumps for each index except 0 as INFINITY.

Start filling distance of each index.

At index i, for each j from 0 to A[i], check if jumps[i] + 1 is less than jumps[i+j]. If jumps[i+j] was filled with jumps to reach index i+j, which was greater than jumps[i] +1, then change jumps[i+j] to jumps[i]+1. Why? Because index i+j can be now be reached from i with only one jump. When i+j is greater than size of array, end of array is reached and fill jumps[N] as jumps[i] +1 and that will be solution. 

Minimum number of jumps to reach end : implementation

#include<stdio.h>
 
#define INFINITY 9999
 
int minimumNumberOfJumps(int a[], int size){
 
    int jumps[size];
    jumps[0] = 0;
    for(int i=1; i<size; i++){
 	jumps[i] = INFINITY;
    }
    for(int i=0; i<size; i++){
    	for(int j=1; j<=a[i]; j++){
    	    if(i+j < size){
    		if(jumps[i+j] > jumps[i]+1){
    		    jumps[i+j] = jumps[i]+1;
    		}
    	    }
    	    else{
    		return jumps[i]+1;
    	    }
    	}
    }
    return jumps[size-1];
}
//driver program
int main(){
    int a[] = {1,5,5,3,1,4};
    int size = sizeof(a)/sizeof(a[0]);
    printf("Minimum Jump : %d", minimumNumberOfJumps(a, size));
    return 0;
}

Let’s work out an example: [1,1,2,10,1,1,1,1,1,1,4]

Distance array will be of size 11. jumps[0] =0. Jumps to all indices are then initialize to INFINITY.

For i =0, j = 1
jumps[i +j] =jumps[0+1] =jumps[1] which is INFINITY as of now. Hence jumps[1] can be filled with jumps[i] + 1 which is jumps[0] + 1 = 1.

For i =1 j=1
jumps[i +j] =jumps[1+1] =jumps[2] which is INFINITY as of now. Hence Distance[2] can be filled with Distance[i] + 1 which is Distance[1] + 1 = 2.

For i =2 j=1,2 j =1: jumps[i +j] = jumps[2+1] = jumps[3] which is INFINITY as of now. Hence jumps[3] can be filled with jumps[i] + 1 which is jumps[2] + 1 = 3. jumps[3] =3

j = 2: jumps[i +j] = jumps[2+2] = jumps[4] which is INFINITY as of now. Hence jumps[4] can be filled with jumps[i] + 1 which is jumps[2] + 1 = 3. jumps[4] =3.

Now i =3. j =1,2,3,4,5,6,7,8,9,10. However, i + a[i] > size of array  and hence, solution will be jumps[3] + 1 = 4 and program exits.

Complexity of algorithm to find minimum jumps to reach end of an array using dynamic programming would be O(min(k,N) *N) along space complexity of O(N), where K is maximum jump.