DEV Community

Avin Sharma
Avin Sharma

Posted on • Originally published at avinsharma.com on

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

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read more →

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more