Find the Minimum Number of Jumps to Reach the End of an Array

Jumping through arrays is a classic interview problem that tests your understanding of dynamic programming and greedy approaches. This post explores how to efficiently find the minimum number of jumps required to reach the end of a given array.

Understanding the Problem

We’re given an array of non-negative integers where each element represents the maximum jump length from that position. The goal is to determine the minimum number of jumps needed to reach the last index of the array, starting from the first index. If it’s impossible to reach the end, we return -1.

For example:

• Array: [2, 3, 1, 1, 4]

• Minimum Jumps: 2 (Jump from index 0 to 1, then from 1 to 4)

• Array: [1, 1, 1, 1, 1]

• Minimum Jumps: 4

• Array: [3, 0, 2, 0, 4]

• Minimum Jumps: 2

Dynamic Programming Approach

Dynamic programming offers a systematic way to solve this problem. We create a dp array where dp[i] stores the minimum number of jumps needed to reach index i.

def min_jumps_dp(nums):
    n = len(nums)
    if n <= 1:
        return 0  # Already at the end or only one element

    dp = [float('inf')] * n
    dp[0] = 0  # No jumps needed to reach the starting point

    for i in range(n):
        for j in range(i + 1, min(i + nums[i] + 1, n)):
            dp[j] = min(dp[j], dp[i] + 1)

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


#Example Usage
arr1 = [2, 3, 1, 1, 4]
arr2 = [1, 1, 1, 1, 1]
arr3 = [3, 0, 2, 0, 4]
arr4 = [0]
arr5 = [1,0]

print(f"Minimum jumps for {arr1}: {min_jumps_dp(arr1)}") #Output: 2
print(f"Minimum jumps for {arr2}: {min_jumps_dp(arr2)}") #Output: 4
print(f"Minimum jumps for {arr3}: {min_jumps_dp(arr3)}") #Output: 2
print(f"Minimum jumps for {arr4}: {min_jumps_dp(arr4)}") #Output: 0
print(f"Minimum jumps for {arr5}: {min_jumps_dp(arr5)}") #Output: -1

This approach iterates through the array, updating the minimum jumps for each reachable index. The time complexity is O(n^2), where n is the length of the array.

Greedy Approach

A more efficient greedy approach exists. This approach keeps track of the farthest_reach and the current_reach.

def min_jumps_greedy(nums):
    n = len(nums)
    if n <= 1:
        return 0

    jumps = 0
    current_reach = 0
    farthest_reach = 0

    for i in range(n - 1):
        farthest_reach = max(farthest_reach, i + nums[i])
        if i == current_reach:
            jumps += 1
            current_reach = farthest_reach
            if current_reach >= n - 1:
                break
        if current_reach >= n-1:
          break

    return jumps if current_reach >= n - 1 else -1


#Example Usage
arr1 = [2, 3, 1, 1, 4]
arr2 = [1, 1, 1, 1, 1]
arr3 = [3, 0, 2, 0, 4]
arr4 = [0]
arr5 = [1,0]


print(f"Minimum jumps for {arr1}: {min_jumps_greedy(arr1)}") #Output: 2
print(f"Minimum jumps for {arr2}: {min_jumps_greedy(arr2)}") #Output: 4
print(f"Minimum jumps for {arr3}: {min_jumps_greedy(arr3)}") #Output: 2
print(f"Minimum jumps for {arr4}: {min_jumps_greedy(arr4)}") #Output: -1
print(f"Minimum jumps for {arr5}: {min_jumps_greedy(arr5)}") #Output: -1

The greedy approach has a time complexity of O(n), making it faster than the dynamic programming solution for larger arrays. It iterates through the array only once, updating the reachable indices efficiently.

Choosing the Right Approach

For most cases, the greedy approach is preferred due to its superior time complexity. However, understanding the dynamic programming solution provides a solid foundation for tackling similar problems. The choice depends on the specific constraints and performance requirements of your application.