Minimum Number of Jumps to Reach End

Difficulty: Medium, Asked-in: Google, Amazon, Walmart, Adobe, eBay

Key takeaway: An excellent problem to learn time and space complexity optimization in a dynamic programming problem. The efficient single loop solution is intuitive and worth exploring.

Let’s understand the problem!

An array of positive integers is given, write a program to reach the last index using the minimum number of jumps.

  • We are initially positioned at the first index of array.
  • Each element in array represents the maximum jump length from that position. For example, if A[i] = x, this means that from index i we can jump to any one of the index i+1, i+2 … i+x.
  • Assume that we can always reach the last index.
  • There can be several ways to reach the end using minimum number of jumps. Here our aim is to just return the minimum number of jump count.

Important note: Before moving on to the solutions, we recommend trying this problem on paper for atleast 15 or 30 minutes. Enjoy problem-solving!

Example 1

Input: A[] = [1, 3, 5, 8, 10, 2, 6, 7, 6, 8, 9], Output: 3

Explanation: 1-> 3 -> 8 -> 9 or 1-> 3 -> 10 -> 9

  • Here we have 11 elements in array, so start index = 0, end index = 10
  • A[0] = 1: we can jump from the 0th index to the 1st index.
  • A[1] = 3: We can jump max 3 steps from index 1. In other words, we can reach indices 2, 3, and 4 from the 1st index.
  • A[2] = 5: We can not reach the last index from index 2 because max reachable index from index 2 would be 2 + 5 = 7.
  • A[3] = 8: We can easily reach the last index from index 3 because the max reachable index from index 3 would be 3 + 8 = 11. In other words, we can take 7 step jump from index 3 to reach the last index 10.
  • A[4] = 10: We can easily reach the last index from index 4 because the max reachable index from index 4 would be 4 + 10 = 14. In other words, we can take 6 step jump from index 4 to reach the last index 10.

Example 2

Input: A[] = [2, 3, 1, 1, 4], Output: 2

Explanation: 2->3->4. The minimum number of jumps to reach the last index is 2. We jump 1 step from index 0 to 1, then 3 steps to the last index.

Discussed solution approaches

  • A brute force approach  using recursion
  • A bottom-up approach using dynamic programming
  • An efficient in-place approach  using a single loop
  • Another efficient in-place approach using a single loop

Solution approach 1: A brute force approach  using recursion

Solution idea

There can be many possible ways to reach the end, but we need to find a way using a minimum number of jumps. So one basic solution would be to calculate the jump count of all possible ways to reach the end and return the minimum among those values. The critical question would be: How do we explore all possible ways to reach the end? Let's think!

When there is requirement to explore all possible ways, we can think to apply the idea of recursion i.e. solution of the larger problem using solution of smaller subproblems.

Here is an intuition for a recursive solution: We start from the 0th index and recursively call for all the indices reachable from 0th index. In other words, the minimum number of jumps to reach the last index can be calculated using the minimum number of jumps needed to reach the last index from the index reachable from 0th index. (Think!)

Recursive structure

  • Suppose our initial function call is minJumps (A[], start, end), where end indices of the array A[] are start and end. So from the first index start, we can take a maximum single jump of i number of steps where 1 <= i <= A[start].
  • What would be the smaller subproblem if we take a single jump of i number of steps from the start index? The answer would be simple: Find the minimum number of jumps to reach the last index from (start + i)th index i.e. minJumps (A[], start + i, end).
  • Now, for finding the minimum jump count, we recursively calculate jump count for all possible values of i (1 <= i <= A[start]) and find the minimum among them. We also add 1 because we take one jump to reach index i from the start index (Think!).

For all i reachable from start i.e. i = 1 to A[start]:

minJumps (A[], start, end) = 1 + min (minJump (A[], start + i, end ))

Base case

This is a case of single or zero element array where no jump is required to reach the end. i.e. if (start >= end), we return 0.

Solution pseudocode

int minJump(int A[], int start, int end)
{
    if (start >= end)
        return 0
    int minJumpCount = INX_MAX
    for (int i = 1; i <= A[start] && i < end; i = i + 1)
    {
        int jumpCount = 1 + minJump(A, start + i, end)
        if (jumpCount < minJumpCount)
            minJumpCount = jumpCount
    }
    return minJumpCount
}

Solution analysis

We can think from a simple perspective to calculate all possible ways to reach the end. There are two possibilities for each index from 1 to n - 1: either we take a jump from that index or do not take a jump. So total number of possible ways = 2^(n-1), which is exponential time. Think!

We can also think to analyze it by writing a recurrence relation.

  • Time complexity to reach the end in n size array = T(n)
  • After taking i number of jumps in the start, input size of the smaller sub-problem = n - i. Time complexity of the input size n - i = T(n - i)
  • We are recursively calling for all indexes reachable from the first index. So max possible jump count equals the value of A[start]. In worst case, the value of A[start] can be n - 1 or greater than n - 1. (Think!).
  • Here is the recurrence relation: T(n) = c + ∑(i = 1 to A[start]) T(n - i). If we put A[start] = n - 1, we get the uppar bound: T(n) <= c + ∑(i = 1 to n - 1) T(n - i)
  • We can also write in other way, if we put k = n - i: T(n) <= c + ∑(k = 1 to n - 1) T(k)
  • If we solve the above recurrence using recursion tree method, then the tree of recursive calls has 2^n - 1 leaves. (Think!). Time complexity = T(n) = O(2^n)

So finding the min jump is exponential function of n, which is inefficient. In retrospect, this is not surprising because we are exploring all possibilities. If we create a recursion tree for above approach, we can notice overlapping subproblems.

For example, if we observe the following picture, the sub-problem minJump(2, 5) is coming two times, minJump(3, 5) is coming 3 times, and so on.

minimum number of jumps to reach end recursion tree example

Critical points to notice

  • This is an optimization problem with exponentially large solution space, but only a few solutions will provide the optimal solution. 
  • Sub-problems are overlapping i.e. we are solving same subproblems again and again. 
  • In worst case, the total number of different subproblems is equal to n i.e. sub-problems of size 1, sub-problem of size 2…up to sub-problem of size n. Our time complexity is exponential because these n sub-problems will be repeated during the recursion (Think!)

Solution approach 2: A bottom-up approach using dynamic programming

Solution idea

Since we have identified this as a dynamic programming problem, we can efficiently solve it using a bottom-up approach. We aim to calculate the solution of smaller sub-problems iteratively and store their results in a table.

  • Table structure and size: Only one variable decreases by 1 during the recursion so that we can take one-dimensional table jumps[n] to store solutions of the n different sub-problems (Table size is equal to the total number of sub-problems). Here jumps[i] indicates the minimum number of jumps needed to reach A[i] from A[0].
  • Table initialization: We initialize the table by using the basic solution i.e. jumps[0] = 0. There is no need to jump when there is a single element in the array. We also initialize the remaining position of jumps[] array with the INT_MAX.
  • Iterative structure to fill the table: We can define iterative structure to fill the table using the recursive solution. This approach of storing results in a table is similar to the longest increasing subsequence problem. jumps[i] = min (jumps [j] + 1), For all j < i < j + A[j])
  • Termination and returning final solution: Our final answer will be stored at jumps[n-1], and we return this value.

Solution pseudocode

int minJump(int A[], int n)
{
    int jump[n]
    jump[0] = 0
    for (int i = 1; i < n; i = i + 1)
        jump[i] = INX_MAX
    for (int i = 1; i < n; i = i + 1)
    { 
        for (int j = 0; j < i; j = j + 1)
        {
            if (i <= j + A[j] && jump[j] != INX_MAX)
                jump[i] = min (jump[i], jump[j] + 1)
        }
    }
    return jump[n - 1]
}

Solution analysis

Time complexity = Time complexity of initializing jump[] array + Time complexity of nested loops to store values in jump[] array = O(n) + O(n^2) = O(n^2). Similarly, space complexity = O(n) for using n size jump[] array.

Solution approach 3: An efficient in-place approach  using a single loop

Solution idea

The above dynamic programming solution is much more efficient than a brute force solution. But critical questions are: can we further improve the time complexity, space complexity, or both? Can we try to remove inner loop of the above solution? Can we track the value of minimum jump using some variable?

Here is an improvement insight: From any jump point i, we can reach any index from (i + 1) to (i + A[i]), and there will be some value between range A [i + 1] to A [i + A[i]], which can provide the farthest reach from that range. So we define lower and upper end of the current jump point and calculate the farthest reach in that range. Whenever we reach the upper endpoint of a range, we update the upper end with the value of farthest reach and increment jump count. We continue this process till the value of farthest reachable index is greater than n - 1.

Let's define four variables to simulate the above process:

  • jump: To store the value of jump count. Initially jump = 0.
  • currStart and currEnd: To store the range of the current jump point. Initially currStart = 1, currEnd = A[0].
  • currMaxReach: To store the farthest reach possible in the range [currStart, currEnd]. Initially currMaxReach = A[0].

Solution steps

  • We initialize jump = 0, currStart = 1, currEnd = A[0], currMaxReach = A[0].
  • Now we traverse the array from currStart = 1 to n - 2 and continue updating the currMaxReach. Here currStart will be less than n - 1 because when we reach the last one, we don't need to jump again.
  • Once currStart == currEnd, we trigger jump and update the range of the next jump point. To update the range, we update the value of currEnd with curMaxReach.
  • During the update of currMaxReach, we also need to check If(currMaxReach > n - 1). If it is true, we can directly reach the end of the array from the currStart by taking a single jump. So we increment the value of jump and break the loop.
  • By the end of loop, we return the value stored in jump.

Solution pseudocode

int minJump(int A[], int n)
{
    if (n <= 1)
        return 0
    int jump = 0, currStart = 1
    int currEnd = A[0], currMaxReach = A[0]
    while (currStart < n - 1)
    { 
        currMaxReach = max(currMaxReach, currStart + A[currStart])
        if (currMaxReach >= n - 1) 
	    {
            jump = jump + 1
            break
        }
        if (currStart == currEnd) 
        {
			jump = jump + 1
			currEnd = currMaxReach
		}
        currStart = currStart + 1
    }
    return jump
}

Solution approach 4: Another efficient in-place approach using a single loop

Solution idea

In this approach, we define three variables: currMaxReachstepsCount, and jump. We define both jump and stepsCount variable to the value of first index of array. Here currMaxReach is the maximum we can reach from that index, which is the index plus the value of index (the jump value). So, we keep updating it in each iteration (start = 1 to n - 2) so that whenever we move forward, the variable currMaxReach stores the max reach by using currMaxReach = max(currMaxReach, A[start] + start)

  • Also, at each iteration, we reduce our stepsCount variable by 1. As we move forward, we consume 1 step each time. So, whenever we run out of steps, it means we need to take one jump. So, we increase the jump variable and update the stepsCount variable to the value (currMaxReach - start) i.e. the maximum reach possible from the current index. So, we can take those steps, and then we need to jump again.
  • So, we return jump + 1 as our output in this solution since we only jump after running out of steps. Also, we need to note that: we moved only till the second last element and not the last element since at the last step, we do not need to consume one more step as we are already there and no need to jump more.

Solution pseudocode

int minJump(int A[], int n)
{
    if (n <= 1)
        return 0
    int currMaxReach = A[0]
    int stepsCount = A[0]
    int jump = 0
    for (int start = 1; start < n - 1; start = start + 1)
    {
        currMaxReach = max(currMaxReach, start + A[start])
        stepsCount = stepsCount - 1
        if (stepsCount == 0)
        {
            jump = jump + 1
            stepsCount = currMaxReach - start
        }
    }
    return jump + 1
}

Solution analysis

In both the single loop solution, we are doing constant operations at each iteration. So time complexity = O(n). We are using constant extra space, so space complexity = O(1)

Important note: we recommend transforming the above pseudo-codes into a favorite programming language (C, C++, Java, Python, etc.) and verifying all the test cases. Enjoy programming!

Critical ideas to think!

  • Can we think of implementing the single loop solution by traversing the array from right to left instead of left to right?
  • How would we modify the above approach if there is no guarantee to reach the end? In other words, return true if we can reach the last index, or false otherwise.
  • Does the single solution look like a greedy approach?
  • What would be the space complexity of the recursive solution?
  • How do we modify the above approaches to output the elements involved in reaching the end-point using the minimum number of jumps?

Comparison of time and space complexities

  • Using recursion: Time = O(2^n) , Space = O(n)
  • Using bottom-up approach: Time = O(n^2), Space = O(n)
  • Using a single loop : Time = O(n) , Space = O(1)
  • Another solution using a single loop: Time = O(n), Space = O(1)

Suggested coding problems to practice

Please write in the message below if you find anything incorrect, or if you want to share more insight. Enjoy learning, Enjoy algorithms!

Share feedback with us

More blogs to explore

Our weekly newsletter

Subscribe to get weekly content on data structure and algorithms, machine learning, system design and oops.

© 2022 Code Algorithms Pvt. Ltd.

All rights reserved.