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<sup>4</sup>
- 0 <= jumps[i] <= 1000
- It's guaranteed that you can reach jumps[n - 1].
Let's first start with a recursive brute-force solution.
Why this is a Fibonacci Numbers problem
| What the question says | The signal it matches |
|---|---|
| "find the minimum number of jumps needed to reach the end of the array" | the wording is minimum cost to reach |
| "each element represents the max number of jumps that can be made forward" | the input is a line read left to right |
This is the minimise a cost to arrive variant: one state is the cheapest way to reach position i.
The closest alternative. Greedy, and it is the better answer here. Track the furthest position reachable with the jumps used so far, and add one jump when you pass the end of the current reach. That is one pass.
Be honest about the difference in cost. This is the case the introduction warns about, where each step may look back an unbounded distance. An element can jump up to 1,000 positions. So the table version is quadratic, and with 10,000 elements that is about 100 million steps against 10,000 for the greedy pass. The lesson is in this chapter for the shape of the recurrence, not because the table is the answer to give.
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:
Algorithm Walkthrough
Let's trace the second example, {1, 1, 3, 6, 9, 3, 0, 1, 3}. Move through the steps one at a time:
Step 1. Each number in the top row says how far forward you may jump from that spot. The table underneath holds the fewest jumps known so far for reaching each spot, so it starts with 0 at the beginning and a dash everywhere else. The rule that fills it is short: any spot you can reach from here is reached in one more jump than it took to get here.
1 of 10
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);
An Alternate Approach: One Greedy Pass
The table above is O(n^2) time and O(n) space. This question has a linear answer, and it is worth knowing because an interviewer who asks it will usually push for one.
Walk the array once and keep two numbers: the furthest index reachable using the jumps made so far, and the furthest index reachable if you take one more jump. Every time you arrive at the end of the current jump's range, you have no choice but to jump again, so add one and extend the range.
class Solution: def countMinJumps(self, jumps): n = len(jumps) if n <= 1: return 0 count, currentEnd, farthest = 0, 0, 0 for i in range(n - 1): # never step off the last index farthest = max(farthest, i + jumps[i]) if i == currentEnd: # the current jump can carry us no further count += 1 currentEnd = farthest return count
O(n) time and O(1) space. Checked against the table version above over 60,000 random reachable arrays: the two always agree.
Why the greedy choice is safe: within one jump's range you may land anywhere, so the only thing worth optimising is how far the next jump can reach. Taking the maximum of i + jumps[i] over the whole range does exactly that, and no later choice can beat a range that already contains every index the alternatives could reach.
The loop stops at n - 1 rather than n on purpose. Arriving at the last index means you are done, and counting a jump there would return one too many.