Given an array of integers where each element represents the maximum number of steps that can be made forward from that element, return the minimum number of jumps to reach the end of the array starting from the first element.
Example:
miniJump([1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9]) === 3. The first element is 1, so you can only go to 3. The second element is 3, so you can make at most 3 steps (to 5 or 8 or 9). If you encounter a 0 in the array, just return -1.
Let's start by defining the test cases from the problem statement.
Let's run the test.
Then we'll describe two base cases, for zero-length and unit-length arrays.
And we'll implement a first draft of the function.
We'll continue with a simple one-cell jump (ie, if the value 1 is in the first cell): the only choice is to go forward by one. The array can be decomposed into [1, ...rest] and the problem can be reduced to 1 + miniJump(rest).
When a 2 is encountered, the result should be the minimum of a recursive call on the array with one element removed or two elements removed, incremented by one to account for the current jump. Let's for example compute the answer for [2, 1, 1]: there are two options, removing one or removing two elements. Add one to the score of each and return the minimum.
Let's rewrite the if as a loop to compute the minimum. We don't care if we go beyond the end of the array since the return value of the recursive call is the same with one or zero elements.
It works!
It works, but it's inefficient. Indeed, this O (2n) algorithm computes every possible jump before giving the answer. We will change the order in which we compute solutions from the current depth-first traversal to a breadth-first traversal which will find the shortest path sooner. In other words, instead of finding all paths and then sorting them to find the shortest, we're going to traverse the paths in sorted order right from the start, ensuring that the first path we find is the shortest, thus allowing us to skip all the remaining paths.
Let's first have a look at the performance of the current algorithm.
I don't suggest adding other rows of numbers inside bigJump unless you want to freeze this tab long enough to drink a coffee.
To improve the algorithm, we need to switch from recursion to iteration. See this talk on defunctionalization.
Let's rewrite the function so the whole path's state is visible instead of being kept in the call stack, and instead of computing the subpaths immediately, put them in a queue.
🎉🎉🎉Now that's much better! On a larger input, it takes 4 milliseconds instead of 30 seconds. That's enough optimization for today. See you around! 👋