Minimum Number of Jumps to Reach End

January 10, 2024

Problem #

You are given an array arr of positive integers, representing the maximum number of jumps you can make from each index. You start from the first index and must reach the last index. Find the minimum number of jumps required to reach the end of the array.

Solution #

To solve this problem, we can use dynamic programming (DP). We will create a new DP array dp and initialize it with infinity except for the first element, which is set to 0. Then, we iterate through the array and update each cell of dp by considering the minimum number of jumps required from all previous indices.

Code: #

def minJumps(arr):
    n = len(arr)
    
    # If the array has only one element
    if n <= 1:
        return 0

    # If the first element is 0, it's not possible to move forward
    if arr[0] == 0:
        return -1

    jumps = [float('inf')] * n
    jumps[0] = 0

    # Building the jumps array using dynamic programming
    for i in range(1, n):
        for j in range(i):
            if i <= j + arr[j] and jumps[j] != float('inf'):
                jumps[i] = min(jumps[i], jumps[j] + 1)
                break

    return jumps[-1] if jumps[-1] != float('inf') else -1

# Example usage
arr = [2, 3, 1, 1, 2, 4, 2, 0, 1, 1]
print(minJumps(arr))  # Output will be the minimum number of jumps

Explanation: #

• n is the length of the array arr.
• We initialize a jumps array where jumps[i] will eventually store the minimum number of jumps to reach index i.
• We iterate through each element of arr. For each element, we look back at all previous elements and check if that element can jump to the current element. If it can, we update the jumps[i] with the minimum number of jumps needed to reach i.
• If the end of the array is reachable, jumps[-1] will contain the minimum number of jumps; otherwise, it will be float('inf'), and we return -1 to indicate it’s not possible to reach the end.

Time Complexity #

O(n^2), where ’n’ is the length of the array. This is because we are iterating through each index twice (once for updating minJumps and once for updating dp).

Space Complexity #

O(n) as we create a new DP array of size ’n’ to store the minimum number of jumps for each index.