Minimum number of jumps II

I am trying to solve the GeeksForGeeks problem Minimum number of jumps:

Given an array of N integers arr[] where each element represents the max length of the jump that can be made forward from that element. Find the minimum number of jumps to reach the end of the array (starting from the first element). If an element is 0, then you cannot move through that element.

Note: Return -1 if you can't reach the end of the array.

I couldn't solve this problem for O(n) time complexity, so I looked around and came across the following article link: https://www.enjoyalgorithms.com/blog/minimum-number-of-jumps-to-reach-end

I understood that we can apply a greedy algorithm to keep track of the the maxPossibleStep that we can take in the current range. But the algorithm suggested in that explanation fails to realize we can't really move forward when, after the current range is over and it's time to step into the next range, it finds that the current position contains zero.

Instead, the algorithm suggested in that article then moves ahead assuming the maxPossibleStep encountered in previous range.

Here is the initial algorithm that I found:

static int minJumps(int[] arr){
    int n = arr.length; 
    if(n <= 1) return 0;   
    int maxReach = arr[0];
    int stepsCount = arr[0];
    int jumps = 0;
    //   boolean isReachable = false;
    int start = 1;
    while(start < n-1){
        maxReach = Math.max(maxReach, start+arr[start]);
        stepsCount--;
        if(stepsCount == 0){
            if(arr[start] == 0) return -1;
            jumps++;
            stepsCount = maxReach-start;
        }
        start++;
    }
    if(jumps == 0 && stepsCount > 0) return 1;  
    return jumps==0?-1:jumps+1;         
}

But this code fails for the following input

N = 15
arr[] = 9 10 1 2 3 4 8 0 0 0 0 0 0 0 1

...because stepsCount will become zero at i == 9 where arr[start] will be zero. Here I am simply returning -1 without considering the previous options, like I can reach element 8 then I can reach the end.

But it will pass for the following:

N = 4
arr[] = 2 1 0 3

... because here either from index 2 or 1 we can't reach index 3

So I came up with the following modification

static int minJumps(int[] arr){       
    int n = arr.length;
    if(n <= 1) return 0;
    int maxReach = arr[0];
    int stepsCount = arr[0];
    int jumps = 0;
    int start = 0;
    //   boolean isReachable = false;
    int i = 1;
    while(i < n-1){
        if(arr[i] != 0) maxReach = Math.max(maxReach, i+arr[i]);
        stepsCount--;
        if(stepsCount == 0){
            // this block checks if we have prev option then try those
            if(arr[i] == 0){
                if(start == i) return -1;
                i = start+2;
                stepsCount = arr[start+1];
                maxReach = arr[start+1];
                //   stepsCount--;
                continue;
            }
            jumps++;
            start = i;
            stepsCount = maxReach-i;
        }
        i++;
    }
    if(stepsCount > 0 || jumps != 0) return jumps+1;  
    return -1;
}

Here I am keeping an additional variable called start (don't confuse it with the start in above code, apologies for confusion [above start === i])

Whenever I find that the stepsCount is zero, and it's time to jump to next interval, I check if the current element is zero, I backtrack to start+2 and reset maxReach and stepsCount accordingly.

But the problem with this modified algorithm, is it's not giving me O(n) time complexity. I am getting Time Limit Exceeded.

I am also not very confident that the above approach is really correct.

How can I modify the original algorithm, so it returns the correct result, including for the test case I provided?

The first code version has one issue in the line where -1 is returned:

            if(stepsCount == 0){
                if(arr[start] == 0) return -1;
                jumps++;
                stepsCount = maxReach-start;

This is not correct. It may well be that arr[start] is zero, but that at some previous index a large enough value was found to jump beyond this point. And in the example input you have given that is indeed the case.

Instead, the -1 should be returned when none of the previous values would allow a jump beyond the current start index. That means you should check how maxReach relates to start, or in other words, we should check whether the updated stepsCount is strictly positive.

Here is the correction for that section of code:

            if(stepsCount == 0){
                jumps++;
                stepsCount = maxReach-start;
                if(stepsCount == 0) return -1;