Grokking Dynamic Programming Patterns for Coding Interviews

0% completed

​

Minimum jumps to reach the end

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

.....

.....

.....

Like the course? Get enrolled and start learning!
S

Shan

· 4 years ago

The runtime for brute force seems wrong. In general top down runtime can be inferred by "the branching factor raise to the height of the recursion tree.

For the fibonacci its 2^n because at every point there are 2 decisions i.e. f(n-1) and f(n-2) hence 2^n is accurate.

For this problem the branching factor is not 2. Instead it should be the max(end - start) because that is the recursive call that will trigger the most subcalls. But keep in mind we limit our while loop to not exceed the size of the array to avoid going out of bounds. So the runtime should be O(len(jumps)^n) i.e. [100,1,0,2] would mean in the first call of the recursive methods we would trigger recursion 3 times therefore n-1 resolves to n because we can drop the constant.

S

Sreeraj Punnoli

· 4 years ago

In the example 2 explanation, the index should be 0->1->2->5->8 instead of 0->1->2->3->8, right?

R

Ray

· 4 years ago

This problem and the basic solution (brute force recursive) are very confusing to me.

I was able to brute force (iterate through jumps array in order) to get the answer. Assuming you need to go in-order through the jumps array (no skipping items & can't duplicate), a simple iteration loop (no recursion) works fine.

I realize this is the DP course so recursive top-down with memo is common/expected.

I find the brute force recursive Basic Solution extremely hard to understand. Specifically starting on index + 1 instead of starting from index 0 and using that (index 0) jump distance value.

Show 1 reply
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

import math

class Solution:
  def countMinJumps(self, jumps):

    def dp(index, count, memo):
      
      if (index, count) in memo:
        return memo[(index, count)]

      if index >= len(jumps) - 1:
        return count

      min_count = float('inf')
      
      for i in range(index + 1, index + jumps[index] + 1):
        min_count = min(dp(i, count + 1, memo), min_count)

      memo[(index, count)] = min_count

      return min_count

    return dp(0, 0, {})
M

mailman14736

· a month ago

You should probably mention in the solution that this has a Greedy solution which runs in O(n) and with O(1) space complexity....... since this is listed in the DP section, one might assume that DP is optional, when indeed it is not. Additionally, there is a monotonic stack solution that runs in O(n) with O(n) space complexity, which also beats your DP solution.


def min_jumps(arr):

    n = len(arr)

    if n <= 1:

        return 0

    jumps = 0

    current_end = 0

    farthest = 0

    for i in range(n - 1):  # stop before last index

        farthest = max(farthest, i + arr[i])

        if i == current_end:  # reached boundary → must jump

            jumps += 1

            current_end = farthest

    return jumps