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 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 eg to 5 or 8 or 9.
[ad type=”banner”]
Method 1 (Naive Recursive Approach)
A naive approach is to start from the first element and recursively call for all the elements reachable from first element. The minimum number of jumps to reach end from first can be calculated using minimum number of jumps needed to reach end from the elements reachable from first.
minJumps(start, end) = Min ( minJumps(k, end) ) for all k reachable from start
[pastacode lang=”c” manual=”%23include%20%3Cstdio.h%3E%0A%23include%20%3Climits.h%3E%0A%20%0A%2F%2F%20Returns%20minimum%20number%20of%20jumps%20to%20reach%20arr%5Bh%5D%20from%20arr%5Bl%5D%0Aint%20minJumps(int%20arr%5B%5D%2C%20int%20l%2C%20int%20h)%0A%7B%0A%20%20%20%2F%2F%20Base%20case%3A%20when%20source%20and%20destination%20are%20same%0A%20%20%20if%20(h%20%3D%3D%20l)%0A%20%20%20%20%20return%200%3B%0A%20%0A%20%20%20%2F%2F%20When%20nothing%20is%20reachable%20from%20the%20given%20source%0A%20%20%20if%20(arr%5Bl%5D%20%3D%3D%200)%0A%20%20%20%20%20return%20INT_MAX%3B%0A%20%0A%20%20%20%2F%2F%20Traverse%20through%20all%20the%20points%20reachable%20from%20arr%5Bl%5D.%20Recursively%0A%20%20%20%2F%2F%20get%20the%20minimum%20number%20of%20jumps%20needed%20to%20reach%20arr%5Bh%5D%20from%20these%0A%20%20%20%2F%2F%20reachable%20points.%0A%20%20%20int%20min%20%3D%20INT_MAX%3B%0A%20%20%20for%20(int%20i%20%3D%20l%2B1%3B%20i%20%3C%3D%20h%20%26%26%20i%20%3C%3D%20l%20%2B%20arr%5Bl%5D%3B%20i%2B%2B)%0A%20%20%20%7B%0A%20%20%20%20%20%20%20int%20jumps%20%3D%20minJumps(arr%2C%20i%2C%20h)%3B%0A%20%20%20%20%20%20%20if(jumps%20!%3D%20INT_MAX%20%26%26%20jumps%20%2B%201%20%3C%20min)%0A%20%20%20%20%20%20%20%20%20%20%20min%20%3D%20jumps%20%2B%201%3B%0A%20%20%20%7D%0A%20%0A%20%20%20return%20min%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20function%0Aint%20main()%0A%7B%0A%20%20int%20arr%5B%5D%20%3D%20%7B1%2C%203%2C%206%2C%203%2C%202%2C%203%2C%206%2C%208%2C%209%2C%205%7D%3B%0A%20%20int%20n%20%3D%20sizeof(arr)%2Fsizeof(arr%5B0%5D)%3B%0A%20%20printf(%22Minimum%20number%20of%20jumps%20to%20reach%20end%20is%20%25d%20%22%2C%20minJumps(arr%2C%200%2C%20n-1))%3B%0A%20%20return%200%3B%0A%7D” message=”C” highlight=”” provider=”manual”/]
If we trace the execution of this method, we can see that there will be overlapping subproblems. For example, minJumps(3, 9) will be called two times as arr[3] is reachable from arr[1] and arr[2]. So this problem has both properties (optimal substructure and overlapping subproblems) of Dynamic Programming.
Method 2 (Dynamic Programming)
In this method, we build a jumps[] array from left to right such that jumps[i] indicates the minimum number of jumps needed to reach arr[i] from arr[0]. Finally, we return jumps[n-1].
[pastacode lang=”c” manual=”%23include%20%3Cstdio.h%3E%0A%23include%20%3Climits.h%3E%0A%20%0Aint%20min(int%20x%2C%20int%20y)%20%7B%20return%20(x%20%3C%20y)%3F%20x%3A%20y%3B%20%7D%0A%20%0A%2F%2F%20Returns%20minimum%20number%20of%20jumps%20to%20reach%20arr%5Bn-1%5D%20from%20arr%5B0%5D%0Aint%20minJumps(int%20arr%5B%5D%2C%20int%20n)%0A%7B%0A%20%20%20%20int%20*jumps%20%3D%20new%20int%5Bn%5D%3B%20%20%2F%2F%20jumps%5Bn-1%5D%20will%20hold%20the%20result%0A%20%20%20%20int%20i%2C%20j%3B%0A%20%0A%20%20%20%20if%20(n%20%3D%3D%200%20%7C%7C%20arr%5B0%5D%20%3D%3D%200)%0A%20%20%20%20%20%20%20%20return%20INT_MAX%3B%0A%20%0A%20%20%20%20jumps%5B0%5D%20%3D%200%3B%0A%20%0A%20%20%20%20%2F%2F%20Find%20the%20minimum%20number%20of%20jumps%20to%20reach%20arr%5Bi%5D%0A%20%20%20%20%2F%2F%20from%20arr%5B0%5D%2C%20and%20assign%20this%20value%20to%20jumps%5Bi%5D%0A%20%20%20%20for%20(i%20%3D%201%3B%20i%20%3C%20n%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20jumps%5Bi%5D%20%3D%20INT_MAX%3B%0A%20%20%20%20%20%20%20%20for%20(j%20%3D%200%3B%20j%20%3C%20i%3B%20j%2B%2B)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(i%20%3C%3D%20j%20%2B%20arr%5Bj%5D%20%26%26%20jumps%5Bj%5D%20!%3D%20INT_MAX)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20jumps%5Bi%5D%20%3D%20min(jumps%5Bi%5D%2C%20jumps%5Bj%5D%20%2B%201)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20break%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%20%20%20return%20jumps%5Bn-1%5D%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20function%0Aint%20main()%0A%7B%0A%20%20%20%20int%20arr%5B%5D%20%3D%20%7B1%2C%203%2C%206%2C%201%2C%200%2C%209%7D%3B%0A%20%20%20%20int%20size%20%3D%20sizeof(arr)%2Fsizeof(int)%3B%0A%20%20%20%20printf(%22Minimum%20number%20of%20jumps%20to%20reach%20end%20is%20%25d%20%22%2C%20minJumps(arr%2Csize))%3B%0A%20%20%20%20return%200%3B%0A%7D” message=”C” highlight=”” provider=”manual”/]
Output:
Minimum number of jumps to reach end is 3
Time Complexity: O(n^2)
[ad type=”banner”]
Method 3 (Dynamic Programming)
In this method, we build jumps[] array from right to left such that jumps[i] indicates the minimum number of jumps needed to reach arr[n-1] from arr[i]. Finally, we return arr[0].
[pastacode lang=”c” manual=”int%20minJumps(int%20arr%5B%5D%2C%20int%20n)%0A%7B%0A%20%20%20%20int%20*jumps%20%3D%20new%20int%5Bn%5D%3B%20%20%2F%2F%20jumps%5B0%5D%20will%20hold%20the%20result%0A%20%20%20%20int%20min%3B%0A%20%0A%20%20%20%20%2F%2F%20Minimum%20number%20of%20jumps%20needed%20to%20reach%20last%20element%0A%20%20%20%20%2F%2F%20from%20last%20elements%20itself%20is%20always%200%0A%20%20%20%20jumps%5Bn-1%5D%20%3D%200%3B%0A%20%0A%20%20%20%20int%20i%2C%20j%3B%0A%20%0A%20%20%20%20%2F%2F%20Start%20from%20the%20second%20element%2C%20move%20from%20right%20to%20left%0A%20%20%20%20%2F%2F%20and%20construct%20the%20jumps%5B%5D%20array%20where%20jumps%5Bi%5D%20represents%0A%20%20%20%20%2F%2F%20minimum%20number%20of%20jumps%20needed%20to%20reach%20arr%5Bm-1%5D%20from%20arr%5Bi%5D%0A%20%20%20%20for%20(i%20%3D%20n-2%3B%20i%20%3E%3D0%3B%20i–)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20arr%5Bi%5D%20is%200%20then%20arr%5Bn-1%5D%20can’t%20be%20reached%20from%20here%0A%20%20%20%20%20%20%20%20if%20(arr%5Bi%5D%20%3D%3D%200)%0A%20%20%20%20%20%20%20%20%20%20%20%20jumps%5Bi%5D%20%3D%20INT_MAX%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20we%20can%20direcly%20reach%20to%20the%20end%20point%20from%20here%20then%0A%20%20%20%20%20%20%20%20%2F%2F%20jumps%5Bi%5D%20is%201%0A%20%20%20%20%20%20%20%20else%20if%20(arr%5Bi%5D%20%3E%3D%20n%20-%20i%20-%201)%0A%20%20%20%20%20%20%20%20%20%20%20%20jumps%5Bi%5D%20%3D%201%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Otherwise%2C%20to%20find%20out%20the%20minimum%20number%20of%20jumps%20needed%0A%20%20%20%20%20%20%20%20%2F%2F%20to%20reach%20arr%5Bn-1%5D%2C%20check%20all%20the%20points%20reachable%20from%20here%0A%20%20%20%20%20%20%20%20%2F%2F%20and%20jumps%5B%5D%20value%20for%20those%20points%0A%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20min%20%3D%20INT_MAX%3B%20%20%2F%2F%20initialize%20min%20value%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20following%20loop%20checks%20with%20all%20reachable%20points%20and%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20takes%20the%20minimum%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20(j%20%3D%20i%2B1%3B%20j%20%3C%20n%20%26%26%20j%20%3C%3D%20arr%5Bi%5D%20%2B%20i%3B%20j%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(min%20%3E%20jumps%5Bj%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20min%20%3D%20jumps%5Bj%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%20%20%20%20%20%20%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Handle%20overflow%20%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(min%20!%3D%20INT_MAX)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20jumps%5Bi%5D%20%3D%20min%20%2B%201%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20jumps%5Bi%5D%20%3D%20min%3B%20%2F%2F%20or%20INT_MAX%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20return%20jumps%5B0%5D%3B%0A%7D” message=”C” highlight=”” provider=”manual”/]
Time Complexity: O(n^2) in worst case.
[ad type=”banner”]