Programming Interview Question: Minimum Jumps Recursive Approach

Problem:-

Given an array of non-negative integers, find out the minimum number of junmps required to reach the end of that array

For example: - 1, 4, 3, 7, 1, 2, 6, 7, 6, 10
Output:- 3 jumps

This video explains the recursive solution to find the minimum number of jumps required to reach the end of an array. The algorithm is explained by walking through an example and visualization of the same.

[mbobak]

It sounds like a dynamic programming problem, however should it be solved by a greedy approach? You just look at next array[i] elements and take the (pseudo)maximal element. Each (pseudo)maximal element represents a jump and so you just need to count visited elements.  So array[0] = 1, I have only one option and so I jump at array[1] = 4. Now I have 4 options: 3, 7, 1, 2. I choose 7 and it is the end of the algorithm, because I can reach the end of the array. And so the answer is that I need 3 jumps. It is clearly that time complexity is O(n) and space complexity is O(1). What  do you think about this approach?

[saitejdandge]

public static int minJumps(int[] a, int currentIndex, int sum) {
if (currentIndex >= a.length - 1)
return sum;

int res = Integer.MAX_VALUE;
for (int i = 1; i <= a[currentIndex]; i++) {
res = Math.min(res, minJumps(a, i + currentIndex, sum + 1));
}
return res;
}

[shubhamk]

please also provide the recursive code for this

[IDeserve]

Dear Friends,

If you like our content and would like us to continue making great content for you, please spread the word about IDeserve.
A share/appreciation from you on social network would mean the world to us!


Thanks,
-Team IDeserve.

[studyonline]

You haven't covered the case when 0 is present in the array