Sample Input: [1, 5, 1, 1, 2, 1, 2]
Sample Output: 2 (1 -> 5 -> 2), we jump from index 0 to 1 (1 -> 5) because we can jump 1 unit far from there and then we jump from index 1 to 6 (5 -> 2) because we can jump 5 units from there and we reach the end in 2 jumps.
O(n^2) Time | O(n) Space
My first thought was, this looks like a dynamic programming question. So I basically wanted to maintain an array of same size as the input which would contain what is the minimum jumps to reach any particualr index.
How do we do that? First we initialize the shortest array with infinity. The idea was to have two loops
i(0 -> n-1) and
j(0 -> i) and check if we could reach i from j and if we can, is
shortest[j] + 1 < shortest[i]. If
shortest[j] + 1 < shortest[i] then
shortest[i] = shortest[j] + 1. After both the loops are done we return last element of the
O(n) Time | O(1) Space
Yes this can be done in O(n) time and constant space. Its hard to come up with, but this kind of looks like one of those dynamic problem which could be done in a single pass.
Lets take a look at the problem once again. At any given index we have the maximum distance we could jump if we were standing there. So basically we might have two choices, to either continue the previous jump(lets say we were jumping from index 0 to 5, instead of stopping at 3 we continue our jump to 5) or to start a new jump from the current index.
So at any given point we have our maximum reach, and we keep updating our maximum reach as we keep moving forward. We also maintain a steps variable which is there to basically keep track of how many steps do we have left before we can commit to a jump. When steps reach 0, we assign the current maximum reach as the num of remaining steps because when steps reach 0 that means we are standing at that index and the largest jump from here would be the maximum reach we have been maintaining.
def minNumberOfJumps(array): # Time: O(n) # Space: O(1) if len(array) == 1: return 0 max_reach_index = array steps = array jumps = 0 for i in range(1, len(array) - 1): steps -= 1 max_reach_index = max(max_reach_index, i + array[i]) if steps == 0: jumps += 1 steps = max_reach_index - i # Because we are going till the second last index # we will either have previous unfinished jump or # a new jump starts at second last index either way # we need to add a jump. jumps += 1 return jumps