How to find minimum number of jumps to reach the end of the array in O(n) time

Question

Question

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)

Found multiple ways from Dynamic Programming approach to other linear approaches. I am not able to understand the approach which is said to linear in time. HERE is the link where a linear approach is proposed.

I am not able to understand it at all. What I could understand is that author is suggesting to do a greedy approach and see if we reach end .. if not then backtrack ?

Answer 1

Here is another solution. In this solution, the worst-case complexity is O(n) while the average-case complexity is less than O(n). I don't know how to do average-case complexity analysis. So, I can't tell the exact average-case complexity. But yeah it is faster than 99.22% of submissions on leet code.

def minJumps(self, arr, n):
    current_w=0 # current_index
    last_w=n-1  # last_index
    max_reach=0 # value of index upto which we have analysed array for optimum solution
    max_jumps=arr[0]   # maximum jumps that can be taken from a current_index
    hop=0            # total jumps
    
    while current_w<last_w:
        max_jumps=arr[current_w]
        
        if max_jumps==0:
            return -1
        
        if max_jumps==1:
            max_reach=max_jumps+current_w
            current_w+=1
            
        elif max_jumps<last_w-current_w:     # if maximum steps does not reach to last index
            can_jump_to=arr[max_reach+1:max_jumps+current_w+1]         # subarray in which we have to search for a wall,jumping to which can take us to required solution
            jump_to=max(range(len(can_jump_to)),key=lambda x: x+can_jump_to[x])+max_reach+1 # finding index of wall whoose definition mentioned in above comment
            max_reach=max_jumps+current_w    #updating max_reach
            current_w=jump_to       #updating current position
            
        else:
            current_w=last_w
            
        hop+=1
    return hop

Answer 2

Just in case you need to write a python solution for the greedy approach this code will get you covered for the above problem :)

def minJumps(self, arr, n):
    #code here
    if(n <= 1):
        return(0)
    if(arr[0] == 0):
        return -1
    maxrange, step = arr[0], arr[0]
    jumps = 1
    for i in range(1,n):
        if (i == len(arr) - 1): 
            return jumps
        maxrange = max(maxrange, i+arr[i])
        step -= 1
        if(step == 0):
            jumps += 1
            if(i>=maxrange):
                return -1
            step = maxrange - i
    return(jumps)

Answer 3

Another O(n) Solution With the best explanation The following solution provides with o(n) time complexity For solving minimum jumps to reach the end of the array, For every jump index, we consider need to evaluate the corresponding step values in the index and using the index value divides the array into sub-parts and find out the maximum steps covered index.

Following code and explanation will give you a clear idea:

In each sub-array find out the max distance covered index as the first part of the array, and the second array

Input Array : {1, 3, 5, 9, 6, 2, 6, 7, 6, 8, 9} -> index position starts with 0
Steps :
Initial step is considering the first index and incrementing the jump
Jump = 1
1, { 3, 5, 9, 6, 2, 6, 7, 6, 8, 9} -> 1 is considered as a first jump

next step
From the initial step there is only one step to move so
Jump = 2
1,3, { 5, 9, 6,2, 6, 7, 6, 8, 9} -> 1 is considered as a first jump

next step
Now we have a flexibility to choose any of {5,9,6} because of last step says we can move upto 3 steps
Consider it as a subarray, evaluate the max distance covers with each index position
As {5,9,6} index positions are {2,3,4} 
so the total farther steps we can cover:
{7,12,10} -> we can assume it as {7,12} & {10} are 2 sub arrays where left part of arrays says max distance covered with 2 steps and right side array says max steps cover with remaining values

next step:
Considering the maximum distanc covered in first array we iterate the remaining next elements
1,3,9 {6,2, 6, 7, 6, 8, 9}
From above step ww already visited the 4th index we continue with next 5th index as explained above
{6,2, 6, 7, 6, 8, 9} index positions {4,5,6,7,8,9,10}
{10,7,12,14,14,17,19}
Max step covers here is 19 which corresponding index is 10

Code

//
//  Created by Praveen Kanike on 07/12/20.
//

#include <iostream>
using namespace std;

// Returns minimum number of jumps
// to reach arr[n-1] from arr[0]
int minJumps(int arr[], int n)
{
    // The number of jumps needed to
    // reach the starting index is 0
    if (n <= 1)
        return 0;

    // Return -1 if not possible to jump
    if (arr[0] == 0)
        return -1;

    // stores the number of jumps
    // necessary to reach that maximal
    // reachable position.
    int jump = 1;
    
    // stores the subarray last index
    int subArrEndIndex = arr[0];
    
    int i = 1;
    
    //maximum steps covers in first half of sub array
    int subArrFistHalfMaxSteps = 0;
    
    //maximum steps covers in second half of sub array
    int subArrSecondHalfMaxSteps =0;
    // Start traversing array
    for (i = 1; i < n;) {
        
        subArrEndIndex = i+subArrEndIndex;
        // Check if we have reached the end of the array
        if(subArrEndIndex >= n)
            return  jump;
        
        int firstHalfMaxStepIndex = 0;
        //iterate the sub array and find out the maxsteps cover index
        for(;i<subArrEndIndex;i++)
        {
            int stepsCanCover = arr[i]+i;
            if(subArrFistHalfMaxSteps < stepsCanCover)
            {
                subArrFistHalfMaxSteps = stepsCanCover;
                subArrSecondHalfMaxSteps = 0;
                firstHalfMaxStepIndex = i;
            }
            else if(subArrSecondHalfMaxSteps < stepsCanCover)
            {
                subArrSecondHalfMaxSteps = stepsCanCover;
            }
        }
        if(i > subArrFistHalfMaxSteps)
            return -1;
        jump++;
        //next subarray end index and so far calculated sub array max step cover value
        subArrEndIndex = arr[firstHalfMaxStepIndex];
        subArrFistHalfMaxSteps  = subArrSecondHalfMaxSteps;
    }

    return -1;
}

// Driver program to test above function
int main()
{
    int arr[] = {100, 3, 5, 9, 6, 2, 6, 7, 6, 8, 9};
    int size = sizeof(arr) / sizeof(int);

    // Calling the minJumps function
    cout << ("Minimum number of jumps to reach end is %d ",
            minJumps(arr, size));
    return 0;
}

Answer 4

Many of the answers here so far are great, but I feel I can help explain why the algorithm is correct and the intuition behind it.

I like this problem because it's one where the intuitive dynamic programming approach runs in O(n^2) worst-case, and a greedy approach (the one that motivated this question) runs in O(n) worst-case (it actually only visits each element of the array once). This algorithm is also for me somewhat reminiscent of Dijkstra's algorithm which solves another single-source shortest-path problem and that is also greedy.

To start, remember from the problem statement that A[i] holds the maximum position you can jump to from that index, but you can take a shorter jump from i if A[i]>1, so a shortest sequence of jumps from i=0 could be one with shorter jumps than what's allowed on each index. This is important, since you will see that the algorithm never considers those smaller jumps or their locations explicitly.

Second, it helps to think of the algorithm that you mentioned as one that gives itself "strands of rope" (steps = maxReach - i;) to reach the end, and that it consumes this rope (steps--;) as it tries to advance through the array.

Third, note that the algorithm is not keeping track of the specific indices i that may be part of a shortest sequence from the beginning to the end of the input array A. In fact, the algorithm only increases the variable jump (it gives itself a new strand of rope) when it "runs out of rope" (from the previous strand), so that it can keep iterating in the main loop to "try" to reach the end.

More specifically for the algorithm to be correct it needs to:

1. Keep track of "how far it can reach" (maxReach) from each location i as it moves forward through the array. Note that this quantity is updated for each location even if it's clear already at that moment that reaching that new location will require it to take more "jumps" as you exceed the number of steps (i.e. you run out of rope) that you gave yourself earlier, even if no shortest path would actually visit that element. The goal of these updates is to identify how far the next jump could reach so that it can give itself that much rope once it exhausted the current one.

2. Account for the minimum number of jumps (jumps) you must take if you want to continue iterating through the array to reach the end, as you run out of rope (steps) from the previous strand.

---

The algorithm that you linked to, for reference:

public class Solution {
    public int jump(int[] A) {
        if (A.length <= 1)
            return 0;
        int maxReach = A[0];
        int step = A[0];
        int jump = 1;
        for (int i = 1; i < A.length; i++) {
            if (i == A.length - 1)
                return jump;
            if (i + A[i] > maxReach)
                maxReach = i + A[i];
            step--;
            if (step == 0) {
                jump++;
                step = maxReach - i;
            }
        }
        return jump;
    }
}

Answer 5

static void minJumps(int a[] , int n)
{
    int dp[] = new int[n];
    dp[0] = 0;  //As the min jumps needed to get to first index is zero only.
    //Fill the rest of the array with INT_MAX val so we can make math.min comparisions.
    for(int i=1;i<n;i++)
        dp[i] = Integer.MAX_VALUE;

    for(int i=1;i<n;i++)
    {
        for(int j=0;j<i;j++)
        {   //If we have enough jumps from the position j to reach i. 
            if(j+a[j]>=i)    
            {   //Take the min of current stored value & jumps req to 
              //reach i from j by getting jumps req to reach j plus 1.
              //(Plus 1 because since we have enough jumps to reach 1 from j we 
              //simply add 1 by taking the jumps required to reach j.)
                dp[i] = Math.min(dp[i],dp[j]+1);
            }
        }
    }

    //If first element has zero jumps in store or if the final jumps value 
    //becomes MAX value because there's an element in between which gives zero
    //jumps.
    if(a[0]==0 || dp[n-1] == Integer.MAX_VALUE ) 
    System.out.println("-1");

    else System.out.println(dp[n-1]);
}

Answer 6

The time complexity of the solution proposed on the site is linear because you only iterate over the array once. The algorithm avoids the inner iteration of my proposed solution by using some clever tricks.

The variable maxReach stores at all time the maximal reachable position in the array. jump stores the amount of jumps necessary to reach that position. step stores the amount of steps we can still take (and is initialized with the amount of steps at the first array position)

During the iteration, the above values are updated as follows:

First we test whether we have reached the end of the array, in which case we just need to return the jump variable.

Next we update the maximal reachable position. This is equal to the maximum of maxReach and i+A[i] (the number of steps we can take from the current position).

We used up a step to get to the current index, so steps has to be decreased.

If no more steps are remaining (i.e. steps=0, then we must have used a jump. Therefore increase jump. Since we know that it is possible somehow to reach maxReach, we initialize the steps to the amount of steps to reach maxReach from position i.

public class Solution {
    public int jump(int[] A) {
        if (A.length <= 1)
            return 0;
        int maxReach = A[0];
        int step = A[0];
        int jump = 1;
        for (int i = 1; i < A.length; i++) {
           if (i == A.length - 1)
                return jump;
            if (i + A[i] > maxReach)
                maxReach = i + A[i];
            step--;
            if (step == 0) {
                jump++;
                step = maxReach - i;
            } 
        }
        return jump;
    }
}

Example:

int A[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}
int maxReach = A[0];     // A[0]=1, so the maximum index we can reach at the moment is 1.
int step = A[0];         // A[0] = 1, the amount of steps we can still take is also 1.
int jump = 1;            // we will always need to take at least one jump.

/*************************************
 * First iteration (i=1)
 ************************************/
if (i + A[i] > maxReach) // 1+3 > 1, we can reach further now!
    maxReach = i + A[i]  // maxReach = 4, we now know that index 4 is the largest index we can reach.

step--                   // we used a step to get to this index position, so we decrease it
if (step == 0) {
    ++jump;              // we ran out of steps, this means that we have made a jump
                         // this is indeed the case, we ran out of the 1 step we started from. jump is now equal to 2.
                         // but we can continue with the 3 steps received at array position 2.
    steps = maxReach-i   // we know that by some combination of 2 jumps, we can reach  position 4.
                         // therefore in the current situation, we can minimaly take 3
                         // more steps to reach position 4 => step = 3
}

/*************************************
 * Second iteration (i=2)
 ************************************/
if (i + A[i] > maxReach) // 2+5 > 4, we can reach further now!
    maxReach = i + A[i]  // maxReach = 7, we now know that index 7 is the largest index we can reach.

step--                   // we used a step so now step = 2
if (step==0){
   // step 
}

/*************************************
 * Second iteration (i=3)
 ************************************/
if (i + A[i] > maxReach) // 3+8 > 7, we can reach further now!
    maxReach = i + A[i]  // maxReach = 11, we now know that index 11 is the largest index we can reach.

step--                   // we used a step so now step = 1
if (step==0){
   // step 
}

/*************************************
 * Third iteration (i=4)
 ************************************/
if (i + A[i] > maxReach) // 4+9 > 11, we can reach further now!
    maxReach = i + A[i]  // maxReach = 13, we now know that index 13 is the largest index we can reach.

step--                   // we used a step so now step = 0
if (step == 0) {
    ++jump;              // we ran out of steps, this means that we have made a jump.
                         // jump is now equal to 3.
    steps = maxReach-i   // there exists a combination of jumps to reach index 13, so
                         // we still have a budget of 9 steps
}


/************************************
 * remaining iterations
 ***********************************
// nothing much changes now until we reach the end of the array.

My suboptimal algorithm which works in O(nk) time with n the number of elements in the array and k the largest element in the array and uses an internal loop over array[i]. This loop is avoided by the below algorithm.

Code

public static int minimum_steps(int[] array) {
    int[] min_to_end = new int[array.length];
    for (int i = array.length - 2; i >= 0; --i) {
        if (array[i] <= 0)
            min_to_end[i] = Integer.MAX_VALUE;
        else {
            int minimum = Integer.MAX_VALUE;
            for (int k = 1; k <= array[i]; ++k) {
                if (i + k < array.length)
                    minimum = Math.min(min_to_end[i+k], minimum);
                else
                    break;
            }
            min_to_end[i] = minimum + 1;
        }
    }
    return min_to_end[0];
} 

Answer 7

I have done this with Python. Less complex code with simple terms. This might help you.

def minJump(a):
    end=len(a)
    count=0
    i=a[0]
    tempList1=a
    while(i<=end):
        if(i==0):
            return 0
        tempList1=a[count+1:count+i+1]
        max_index=a.index(max(tempList1))
        count+=1
        i=a[max_index]
        end=end-max_index
    return count+1

Answer 8

Okay, it took me good amount of time to wrap my head around the O(n) algo, I will try to explain the logic to my best simplest possible:

At each "i" in the array, you know with that value what is the currentFarthest value, you can reach up to, & also the currentEnd value, whenever you hit the currentEnd value, you know its time to make a jump & update currentEnd with currentFarthest.

The picture below might help :

Answer 9

Simple python code for the Minimum number of jumps to reach end problem.

ar=[1, 3, 6, 3, 2, 3, 6, 8, 9, 5]
minJumpIdx=0
res=[0]*len(ar)
i=1
while(i<len(ar) and i>minJumpIdx):
    if minJumpIdx+ar[minJumpIdx]>=i:
        res[i]=res[minJumpIdx]+1
        i+=1
    else:
        minJumpIdx+=1
if res[-1]==0:
    print(-1)
else:
    print(res[-1])

Answer 10

Here is the basic intuition regarding the above problem's greedy approach and rest are the code requirements.

Given array is Input: a[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}.

Now we start from the 1st element i.e i=0 and a[i] = 1. So seeing this we can take at most a jump of size 1, so since we don't have any other choice so we make this step happen.

Currently we are at i=1 and a[i]=3. So we currently can make a jump of size 3, but instead we consider all possible jumps we can make from the current location and attain the maximum distance which is within bounds(of the array). So what are our choices? we can make a jump of 1 step, or 2 steps or 3 steps. So we investigate from current location for each size jumps and choose the one which can take us maximum further into the array.

Once we have decided, which one we stick to, we take that jump size and update our number of jumps made so far and also where we can reach at most and how many steps we have now to decide our next move. And that's it. This is how finally we select the best option linearly traversing the array. So this is the basic idea of the algo you might be looking for, next is to code it for the algorithm to work. Cheers!

Hope somebody time travels and finds the intuition helpful !! :) :P "Years late to the party" @Vasilescu Andrei - well said. Sometimes it feels to me that we are time travelers.

Answer 11

Years late to the party , but here is another O(n) solution that made sense for me.

/// <summary>
/// 
/// The actual problem is if it's worth not to jump to the rightmost in order to land on a value that pushes us further than if we jumped on the rightmost.
/// 
/// However , if we approach the problem from the end,  we go end to start,always jumping to the leftmost
/// 
/// with this approach , these is no point in not jumping to the leftmost from end to start , because leftmost will always be the index that has the leftmost leftmost :) , so always choosing leftmost is the fastest way to reach start
/// 
/// </summary>
/// <param name="arr"></param>
static void Jumps (int[] arr)
{
    var LeftMostReacher = new int[arr.Length];
    //let's see , for each element , how far back can it be reached from 

    LeftMostReacher[0] = -1; //the leftmost reacher of 0 is -1

    var unReachableIndex = 1; //this is the first index that hasn't been reached by anyone yet
    //we use this unReachableIndex var so each index's leftmost reacher is  the first that was able to jump to it . Once flagged by the first reacher , new reachers can't be the leftmost anymore so they check starting from unReachableIndex

    // this design insures that the inner loop never flags the same index twice , so the runtime of these two loops together is O(n)

    for (int i = 0; i < arr.Length; i++)
    {
        int maxReach = i + arr[i];

        for (; unReachableIndex <= maxReach && unReachableIndex < arr.Length; unReachableIndex++)
        {

            LeftMostReacher[unReachableIndex] = i;
        }

    }

    // we just go back from the end and then reverse the path

    int index = LeftMostReacher.Length - 1;
    var st = new Stack<int>();

    while (index != -1)
    {
        st.Push(index);
        index = LeftMostReacher[index];
    }

    while (st.Count != 0)
    {
        Console.Write(arr[st.Pop()] + "  ");
    }
    Console.WriteLine();
}
static void Main ()
{
    var nrs = new[] { 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9 };
    Jumps(nrs);
}

Answer 12

Here is another linear solution. The code is longer than the one suggested in the leet code link, but I think it is easier to understand. It is based on a two observations: the number of steps required to reach the i + 1 position is never less than the number of steps required to reach the i position and each element each element assigns its value + 1 to i + 1 ... i + a[i] segment.

public class Solution {
    public int jump(int[] a) {
        int n = a.length;
        // count[i] is the number of "open" segments with value i
        int[] count = new int[n];
        // the number of steps to reach the i-th position
        int[] dp = new int[n];
        Arrays.fill(dp, n);
        // toDelete[i] is the list of values of segments 
        // that close in the i-th position
        ArrayList<Integer>[] toDelete = new ArrayList[n];
        for (int i = 0; i < n; i++)
            toDelete[i] = new ArrayList<>();
        // Initially, the value is 0(for the first element).
        toDelete[0].add(0);
        int min = 0;
        count[0]++;
        for (int i = 0; i < n; i++) {
            // Finds the new minimum. It uses the fact that it cannot decrease. 
            while (min < n && count[min] == 0)
                min++;
            // If min == n, then there is no path. So we can stop.
            if (min == n)
                break;
            dp[i] = min;
            if (dp[i] + 1 < n) {
                // Creates a new segment from i + 1 to i + a[i] with dp[i] + 1 value
                count[dp[i] + 1]++;
                if (i + a[i] < n)
                    toDelete[i + a[i]].add(dp[i] + 1);
            }
            // Processes closing segments in this position.
            for (int deleted : toDelete[i])
                count[deleted]--;
        }
        return dp[n - 1];
    }
}

Complexity analysis:

1. The total number of elements in toDelete lists is O(n). It is the case because at each position i at most one element is added. That's why processing all elements in all toDelete lists requires linear time.

2. The min value can only increase. That's why the inner while loop makes at most n iterations in total.

3. The outer for loop obviously makes n iterations. Thus, the time complexity is linear.