Minumum Number Of Jumps [Python]

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 the same size as the input which would contain what is the minimum jumps to reach any particular 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 shortest array.

O(n) Time | O(1) Space

Yes this can be done in O(n) time and constant space. It is hard to come up with, but this kind of looks like one of those dynamic programming problems which could be done in a single pass.

Let's 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(let's 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[0]
    steps = array[0]
    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