Find Minimum Number of Jumps Requred to Jump From Start to Last Position in an Unsorted Array .Array May Contain The Value 0s & Duplicates as Well (Spacial Case)

You Might Hate me because of Formatting :) Will Update it Asap :)

You are given an array of positive integers. You have to traverse the array with rules that if you are on ith element u can make max arr[i] jumps i.e. if you are at element with value zero you cannot move forward. Find the least number of jumps required to reach the end of the array.
ex: 1 3 5 8 9 2 6 7 6 8 9 .....

This array requires 3 jumps Suggest the algo to find minimum number of jumps.... 1 to 3 to 9 to last 9 ( we want optimal solution )

Greedy Approach(Doesn't Gives Optimal Solution)

Algorithm:
We Know that from ith location we can jump only maximum a[i] , so greedly we will keep goin & icrementing the jump untill we won't reach end of the array.
so in loop i=0 to size of array we will iterate through a[i] & w3ill check if a[i+j]+j ie greater then max or not if its true then we will update the max & repat the same logic. this we will reach to end of the array but doesn't gurantee that it will be optimal. e.g. fro above case it will return 3 jumps but for this case 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9,1,1,1 which requires minimum number of jumps is 3 but this algo will produce jump 4.

Here is Naive but not Optimal Solution

#include
int main()
{
int arr[]={1, 3, 5 ,8 ,9 ,2 ,6, 7, 6, 8, 9};
int size=sizeof(arr)/sizeof(int);

int i=0,jump=0,step,max,j;

while( i< size) { jump++; max=0; step=0; /*computes max distance it can cover in this jump*/ for(j=1;j<=arr[i];j++) { if(arr[i+j]+j>max)
{
max=arr[i+j]+j;
step=j;
}
}
i=i+step;
}

printf("%d ",jump);

}

Time Complexity O(N^2)
Space Compelxity O(1)
Run Here https://ideone.com/ZBQN8 Correct Test Case
Run Here https://ideone.com/apTHY Failed Test Case



2nd Solution Using Dynamic Programming Simple & More Efficient
As We Know Dp can solved using Bottom-Up and Top-Down Appraoch
This Algorithm is Designed By My Friend Sambsiva

Algorithm (Bottom Up Approach but Memozation)

According to Him Lets define a function called hop which is number of steps required to reach the end of array from the given position, So

hop(i) = INT_MAX if a[i] == 0 e.gh. if value is zero at ith position we can't jump

hop(i) = 1 + min(hop(j) where j is from i + 1 to i + a[i]

hop(0) is the required answer

i.e.

#include
#include
int minhops(int a[], int n)
{
int hop[n] ; int i = n;
while(i--)
{
if(a[i] == 0)
hop[i] = INT_MAX;

else
{
if(i + a[i] >= n)
hop[i] = 1;
else
{
int j, min = INT_MAX;
for(j = i + a[i]; j > i; --j)
{

if(hop[j] < min) min = hop[j]; } hop[i] = min + 1; } } } return hop[0];

}

int main() {
 
    int a[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9,1,1,1};
  //{1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9};//{1, 3, 6, 0, 0, 3, 2, 3, 6, 8, 9};
    int n = minhops(a, 14);
 
    if(n != INT_MAX)
        printf("%d\n", minhops(a, 14));
 
 
    return 0;
}
 
 

 Complexity Analysis 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) Time Complexity O(N^2) Space Complexity O(N) Run Here https://ideone.com/v4Go4 Algorithm

(Top-Down Approach-Memoization)

Step 1. Declare an array of size N say jump[N];
where ith position indicates the number of jumps requires to reach from start to this (ith) position in array .

Step 2. Initialize jump[0]=0; indicates to reach oth location form starting location (3which is obviuosly 0) we don't requires any jump.

Step 3. Check size of array and value at 0th location in array 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.so these tow cases are
                  A.If size of array==0 means array is of zero size;
                 B.If value at zero then we can't jump or we can't proceed to next location Step 4. Run Through Loop for remaining elements in array and Initialize jump[i] as infinite. where 
           1<=i<=N.
           Sub-step 4A. (Please Note j runs in inner loop until i<=j+a[j] )
            if jump[i]<jump[j]+1 update jump[i] & repeat until j>i (this whole processing will happen in
            inner loop). e.g. for each ith element this loop will run & tries to figure out optimal/minimum
           number of jumps required to reach this ith position from starting of array .

Step 5. After running above algorithm we will return array[n-1] that will show number of jumps required
to reach last elemnt in array from start.

#include<stdio.h>

#include<limits.h>

int MAX=INT_MAX-1;
unsigned int minJump(int a[], int n)
{
unsigned int *jump= new unsigned int[n];
int i, j;

/*Boundary Cases
1.If n==0 means array is of zero size;
2.If value at zero then we can't jump or we can't proceed to next location
*/

if (n == 0 || a[0] == 0)
return MAX;

jump[0] = 0; //no need to jump at first element

for (i = 1; i < n; i++)
{
jump[i] = MAX; //Initialization of jump[i]

for (j = 0; j < i; j++)
{
//check if jump is possible from j's to ith location where j <=i
if (i<=j+a[j])//because from jth location we can jump up to j+a[j] only
{
//check if better solution available
if ((jump[j] + 1) < jump[i])
jump[i] = jump[j] + 1; //updating jump[i] to optimal jumps
}
}
}

return jump[n-1];

}

int main()
{
int arr[]={1, 3, 6, 0, 0, 3, 2, 3, 6, 8, 9}; ;//{1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9,1,1,1};//{1, 3, 6, 0, 0, 3, 2, 3, 6, 8, 9};

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

printf("%d ",minJump(arr,size));

}
Complexity Analysis
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 jump array.

Time Complexity O(N^2)
Space Complexity O(N)
Run Here https://ideone.com/NIC1x , https://ideone.com/BwAjg