Check correctness of the algorithm for minimum number of jumps in an array

Question

I have an algorithm that is based on a problem where you need to find the minimum number of jumps to reach the end of the array.This problem was asked in geeks for geeks and they do not have a linear time algorithm in my case the algorithm is in linear time but for which test case would my Algorithm fail?.The link for the problem

Link:-http://www.geeksforgeeks.org/minimum-number-of-jumps-to-reach-end-of-a-given-array/

Input: arr[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}

• Starting from the first element we know that the maximum range of the element is 1 hence we can move only one step forward so from 1->3

• Now in the second step we know the range of the element is 3 hence from that step we calculate the max from that range so from 3 we can either chose 5,8,9 and the maximum in this range is 9

• So first move to 9 that is 1->3->9 and then from 9 we move towards the end of the array as we know that nine steps are more than enough to reach the end.

• Corner case is that if we detect a zero at the end we do nothing as we have already reached the end.But if a zero is detected at the start or in a range where 0 is the maximum element in that range to move forward we return a -1 as we cannot move further please tell me if there is a bug in this algorithm.

Answer 1

Yes, this algorithm does not work. Example:

arr[] = {5,2,1,1,1,1,1}

Your algorithm would see 5, then see max number 2, then go to 1 1 1 1. That is: 5,2,1,1,1,1 = 6 jumps.

While the optimal result is: 5 -> 1 (second from end) -> 1 = 3 jumps