Minimum jumps to reach end of array (Dynamic Programming)

hello friends today we are going to see how to reach the end of the array with minimum number of jumps so let's see see this is the array and you can start at index 0 and you have to reach up to index 9 you can take jumps in this array from place to place and you can reach 9 now what can be the length of the jump so it is written here see the maximum jump length from an index will be equal to the number at that index means the element at that index means see here from index 0 you can take a jump of at most two places because the element at index 0 is 2 so you can take a jump of at most 2 places so at most two places means the jump can be of one place or two place okay means from index 0 you can go to index 1 or you can go to index 2 but you cannot go to index 3 because this is the maximum limit of the jump from index 0 only up to index 2 because the element at index 0 is 2 so the length of the jump is at most two places okay so the maximum length of the jump is equal to the number at that index okay this is the meaning let's take one more example suppose you are at 4th index now from this fourth index you can take a jump of at most three places see at most three places means you can reach up to seven so as you can take the jump of at most three places means you can take a jump which is of length one two or three okay means from index for you can reach to fifth index or to sixth index or a length of jump three can take to the seventh place but you cannot go to the eighth place because the length of the jump is at most three places okay now in this way you have to start at the 0th index and have to reach at the ninth index with the minimum number of jumps okay so this is the problem statement now let's see what are these two errands okay so this minimum jumps array is the array in which the minimum jumps required to reach each place is written at that index means suppose at the fourth index I write X jumps okay means you can reach at four from zero with X jumps and X is the minimum number of jumps okay so that is going to be written in this array and what is the jump path array this jump path array holds the value of the location from where we jump okay the last stop of jump means suppose from 0 you go to third index then you go to sixth index and then you go to eighth index just assume this ok so at the third index zero will come that means at the third index the jump was taken from 0th index okay then at the sixth index the jump was taken from the third index so we will write three here then at the 8th index the jump was taken from the sixteen decks so we will write six here so that is this theory means from where we are jumping those locations are going to be written here now let's start to solve this problem so we use two variables I and J to trace this array variable I visits each position in the array and for each position we find out the minimum number of jumps needed to reach that position okay and for every I here for every I J starts from 0 so you can see here is the sample for loop nested for loop just for making you understand how this works so see I starts from 1 to N and J every time starts from 0 and it goes up to I so let's see how do we do this so see I starts from 1 and now we will calculate the number of jumps needed to reach at I means 1 now you will ask me what about 0 so for 0 as it is the starting position only 0 jumps are needed to reach at 0 because we are starting from there so there is no jump needed ok so 0 jumps are needed and this value is hard-coded right so I directly starts from 1 now for every I J starts from 0 so I will start from 0 now see at the jet index what is the value 2 is the value means the maximum length of the jump from 0 can be of length 2 means 2 places so obviously I is in range of J means from index 0 we can reach index I means the x1 so with one jump we can reach from J - I'm so one jump is needed to reach at index one from the starting of the array starting is the 0th index okay and C so we write it here one has the minimum jumps needed to reach index one and in the jump at array we write from where we jump so from where we jump from zero we jump from zero to one okay to reach at index one now as the computation for index one is over let's go ahead means let's increment I and J again starts from zero you will perfectly understand as we go further okay so now see as the value at J is - whether I is in range of J yes it is in range because you can have a jump of two places from J right you can have a jump of at most two places so you can reach I so with one jump you can reach I means for second index you can reach with one jump okay and from where we jumped from the 0th index so I write zero here now let's check another possibility by incrementing J so let's increment J so J comes here now from J whether I is in range yes it is in range because the element or the value here is one and I is one place away right so I is in range means with one jump I can reach I right so how many jumps are needed to reach at second index so the total number of jumps will be first to reach at J index and then 2i index right because from J to I you can reach in one jump but there are some number of jumps required to reach at J because C you have to start from zero then you go to first index and then you go to second index in this case this you go via first index right so from 0 to J how many jumps are needed see here it is written from 0 to J means the first index 1 jump is needed okay this one jump plus from J to I so 1 plus 1 so if you go via 1 if you go why are the first index this first index then you need to jumps right yes so you need 2 jumps to reach at I so here already there is an option of 1 jump means if you directly jump from 0 if you directly jump from 0 to the second index you can go with only 1 jump but if you go via the first index if you go via the first position then you need to jumps so obviously the minimum out of 2 and 1 is 1 so we keep one and we prefer jumping directly from 0 we prefer directly jumping from 0 index so we keep 0 here as it is because we jump from 0 so in this way you have to select the minimum value of jumps okay we can go via many places but you have to select the place from where the number of jumps are minimum ok so as we go further you will be very clear okay now now as has reached I so I is now incremented and J again starts from zero okay now check whether I is in range of J no it is not in range because from jail the maximum length of the jump is two places but I is in the third place so you cannot reach from J to I so you increment J now now check whether it is in range no it is not in range I is not in range of chain so you increment J okay so check whether I is in range of J yes because the value is three so you can reach J so one jump from J to I and how many jumps to reach add J from the starting index 0 from 0 to J how many jumps are needed see one jump is needed Plus this one jump from J to I so one plus one two jumps are needed okay so two jumps to reach at third index right from the starting index wire J means the second index so from 0 first we jumped to second index and then we jump to third index so we went wire to so from where we jumped from to ok from two we jump to the third index so as J has reached I now let's increment I and J will again start from zero okay now let's see again I is not in range of J so increment J now see I is not in range of J so increment J now here yes I is in range of jail so you can jump so this one jump + to reach at J from starting index means from 0th index to reach add how many jumps are needed one jump is needed so this one jump so one plus one is two okay so two jumps are needed and from where we jump see here from where we jump to index four from the second index so I write it here in the jump path array now let's increment J to check other possibilities so I increment jail okay now check whether I is in range of J yes it is in range so we can jump from J to I and to reach add J from the starting position how many jumps are needed it is written here two jumps are needed so - and Plus this one jump okay so two plus one is three jumps if we go via index three see if we go via index three then three jumps are needed right but already to reach to the fourth index we have a path which takes only two jumps and that path goes via the second index why are the second index from zero to two to four this takes only two jumps so we find out minimum from three and two so minimum is two so we keep two as it is and we prefer going no higher second index okay and now as J has reached I we increment I increment I and J again starts from zero right so again I is not in range of J now because J is 2 so J is incremented again I is not in range so J is incremented now I is in range of G right so one jump from J to I and to reach add J one jump is needed so one plus one is two so right to here in this empty box and from where we jump from the second index now let's increment J to check other possibilities so we increment J and we come at index 3 now from J to I yes I is in range of jail so we can jump and to reach at J how many jumps are needed to jumps so 2 plus this one jump so 3 jumps okay so 3 jumps are needed if you go higher node 3 okay so what is minimum out of 3 and 2 2 is minimum so we prefer going via second index right now let's increment J so see yes I is in range of J we can make one jump but to reach and J how many jumps are needed to jumps so 2 plus 1 is 3 so see already we have an option of two jumps and 2 is minimum out of 2 and 3 2 is minimum so we keep 2 as it is ok and now as J has reached I we increment I and J again starts from 0 okay J again starts from 0 now see I is not in range of J so J is incremented I is not in range of j j is incremented i is not in range of J so J is incremented now again I is not in range of J so J is implemented now here yes I is in range of J ok so we can make one jump and to reach at J how many jumps are needed to jumps so 2 plus 1 so 3 jumps as the box is empty directly right three jumps there and from here we come from the fourth index okay now let's increment J to check other possibilities now see whether I is in range of J yes it is so we can make a jump and to reach at J how many jumps are needed is written here 2 so 2 plus 1/2 plus 1 so 2 plus 1 is 3 so 3 jumps are needed to reach at sixth index and as already we have an option of 3 jumps so as 3 is equal to 3 so we don't need to change this value okay we keep 3 as it is and we prefer coming from the 4th index here you can choose any one see why a 4th index also 3 jumps and why a 5th index also 3 jumps so you can prefer anything if you want to prefer the 5th index then you can write 5 here if you want to pray for 4th index you can write 4 here you can take any one now as J has reached I let's increment I so I is incremented and J again starts from 0 okay so again I is not in range of J so increment J and again I is not in range of J so increment J see here not in range not in range then yes it is in range three places from J is I so it is in range so to jump to J how many jumps two jumps are needed and from J to I 1 jump so 2 plus 1 is 3 3 jumps and from here we jump from the 4th index okay now let's increment J so J is incremented see from J to I yes they are in range so to reach to Jett place how many jumps are needed two jumps Plus this one jump so 2 plus 1 is 3 3 is equal to 3 so we keep 3 as it is ok and we increment J so see yes it is in range so to reach 2 J place 3 jumps are needed and this one jump okay so 3 plus 1 is 4 and as 4 is greater than 3 we keep 3 as it is ok so now as J has reached I let's increment I so I is incremented and J again starts from 0 now again not in range then increment J again I is not in range of J so in this way you can go up to here v index now at the 5th index I is in range of J okay so to reach at J how many jumps are needed to jumps Plus this one jump up to I okay so 2 plus 1 is 3 so 3 jumps and from where we jump from the 5th index we jump okay now increment J to check other possibilities so yes it is in range so I is in range of J so to reach add jail how many jumps are needed 3 plus this one jump so 3 plus 1 is 4 but 4 is greater than 3 so we keep 3 as it is and we increment J now yes the value here is 1 and we can reach to the 8th index with one place so we can have one jump and to reach 2 J how many jumps three jumps so 3 plus 1 is 4 4 is greater than 3 so we keep 3 as it is now as J has reached I let's increment I and J will again start from now again we can come up to the fifth index till that index I is not in range and at the fifth index I is in range so to reach up to J two jumps plus we can have one jump so two plus one is three so three jobs so from where we reach the ninth index from the fifth index so I write five here and now I increment J so see yes it is in range so we Chad jet index three jumps are needed and from J to I one jump so three plus one is four but 4 is greater than 3 so we keep three as it is and we increment J now check it is not in range because it the value is 1 so I is not in range of J so we increment J yes it is in range so to reach at jet place three jumps Plus this one jump three plus one is four but 4 is greater than 3 so we don't consider that value we just keep 3 as it is now as J has reached I you have to increment I and when I is incremented I goes greater than n so the loop ends here ok so in this way you can see the answer in the last box so from 0 to the last index 3 jumps are needed this is your answer three jumps are needed and what is the path so you can get the path from this array see at the ninth index from where we jumped from the 5th index okay so we jumped from 5th index to the 9th index okay and to the 5th index from where we jumped from the second index so from second index we came here and for the second index from where we jumped from the 0 this and this is the starting okay so see the path is 0 to 5 and 9 so in this way we find out the minimum number of jumps to reach end and this is the path okay see here is the code so you can see if I is less than J plus area of j j + area of j means what for example you are here okay suppose J is here just an example and I is pointing to the fourth index so J plus area of J means to is j plus area of j is the value so 2 plus 3 is 5 so if I is less than 5 if I is less than or equal to 5 means as I is 4 here 4 is less than or equal to 5 that means I is in range of J that is what we are checking here whether I is in range of J we are checking that by adding the value and J okay and if it is in range then we go inside and as you know in the minimum jump array we feel the value which is minimum minimum of the original value there and value of the jump from J plus 1 okay minimum number of jumps to reach J plus 1 now you will ask me when the box was empty here then how to find out the minimum so I will tell you at first while starting the program you have to initialize all the values as infinity you have to initialize all the values as infinity then this minimum function will work so minimum of infinity and whatever is the value will be the value okay so you have to initialize this array as infinity and then you have to hard code the value at 0th index as because this this is the starting index so this is how this program works hey friends please subscribe to my channel as a post algorithm videos every day and if you want a video on any particular topic then please mention in the comment below thank you

Channel: Vivekanand Khyade - Algorithm Every Day

Views: 72,605

Keywords: minimum number of jumps to reach end of array, dynamic programming, O(n^2) solution, computer science, placement, interview, question, information technology, code, algorithm, program

Id: jH_5ypQggWg

Length: 26min 45sec (1605 seconds)

Published: Sat Jan 06 2018