Problem Statement

Given an array of positive numbers, where each element represents the max number of jumps that can be made forward from that element, write a program to find the minimum number of jumps needed to reach the end of the array (starting from the first element). If an element is 0, then we cannot move through that element.

Example 1:

Input = {2,1,1,1,4}
Output = 3
Explanation: Starting from index '0', we can reach the last index through: 0->2->3->4

Example 2:

Input = {1,1,3,6,9,3,0,1,3}
Output = 4
Explanation: Starting from index '0', we can reach the last index through: 0->1->2->3->8

Constraints:

• 1 <= jumps.length <= 10⁴
• 0 <= jumps[i] <= 1000
• It's guaranteed that you can reach jumps[n - 1].

Let's first start with a recursive brute-force solution.

Basic Solution

We will start with the '0'th index and try all options. So, if the value at the current index is ‘p’, we will try every jump in the range (1 to 'p') from that index. After taking a jump, we recursively try all options from that index.

Here is the code:

The time complexity of the above algorithm is O(2^n), where 'n' is the size of the input array. The 'while loop' can execute a maximum of 'n' times (for the case where we can jump to all the steps ahead) and since in each iteration, the function recursively calls itself, therefore, the time complexity is O(2^n). The space complexity is O(n) which is used to store the recursion stack.

We can clearly see the overlapping subproblem pattern. We can optimize this using memoization to store the results for subproblems.

Top-down Dynamic Programming with Memoization

We can use an array to store the already solved subproblems. Here is the code for this:

Bottom-up Dynamic Programming

Let's try to populate our dp[] array from the above solution, working in the bottom-up fashion. As we saw in the above code, we were trying to find the minimum jumps needed to reach every index (if it is within the range) from the current index. We can use this fact to populate our array.

As we know, every index within the range of current index can be reached in one jump. Therefore, we can say that we can reach every index (within the range of current index) in:

    'jumps to reach current index' + 1

So, while going through all the indexes, we will take the minimum value between the current jump-count and the jumps needed to reach the current index + 1.

Here is the code for our bottom-up dynamic programming approach:

The above solution has a time complexity of O(n^2) (because of the two for loops) and space complexity of O(n) to store dp[].

Fibonacci number pattern

We can clearly see that this problem follows the Fibonacci number pattern. The only difference is that every Fibonacci number is a sum of the two preceding numbers, whereas in this problem every number is the minimum of two numbers (start and end):

    dp[end] = Math.min(dp[end], dp[start]+1);