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

This problem challenges you to determine the minimum number of jumps required to reach the end of an array. Each element in the array represents the maximum number of steps you can jump forward from that position. This tutorial will guide you through the problem statement, sample inputs and outputs, solution steps, and a complete Python program.

Problem Statement

Given an array arr of non-negative integers, where each element indicates the maximum jump length from that position, find the minimum number of jumps needed to reach the last element of the array. If the end of the array is not reachable, return -1.

Sample Input and Output

Example 1:

</>
Copy
# Input:
arr = [2, 3, 1, 1, 4]

# Output:
2

# Explanation:
# Jump from index 0 to index 1 (2 -> 3) and then from index 1 to index 4.

Example 2:

</>
Copy
# Input:
arr = [1, 1, 0, 1]

# Output:
-1

# Explanation:
# It is not possible to move past index 2 because arr[2] is 0.

Solution Approach

The problem can be efficiently solved using a greedy algorithm. Follow these steps to implement the solution:

  1. Initialize Variables: Set maxReach to the maximum index reachable from the first element, step to the number of steps we can take from the current index, and jumps to 1 because the first jump is from index 0.
  2. Iterate Through the Array: For each index, update maxReach as the maximum of its current value and the sum of the current index and its value (i + arr[i]).
  3. Decrement Steps: As you move forward, decrease the step count.
  4. Make a Jump: When the step count reaches 0, increment the jumps counter and reset step to maxReach - current index.
  5. Check Reachability: If at any point the current index is equal to or exceeds maxReach, the end of the array cannot be reached, so return -1.

Python Program

</>
Copy
def min_jumps(arr):
    n = len(arr)
    # If the array has 0 or 1 element, no jump is needed.
    if n <= 1:
        return 0
    # If the first element is 0, it's not possible to move anywhere.
    if arr[0] == 0:
        return -1

    # Initialize maxReach, steps, and jump count.
    maxReach = arr[0]
    step = arr[0]
    jumps = 1

    # Traverse the array starting from the first index.
    for i in range(1, n):
        # If we have reached the end, return the jump count.
        if i == n - 1:
            return jumps

        # Update maxReach.
        maxReach = max(maxReach, i + arr[i])
        
        # Use one step to move to the next index.
        step -= 1
        
        # If no further steps remain, a jump is necessary.
        if step == 0:
            jumps += 1
            # If the current index is at or beyond maxReach, the end is unreachable.
            if i >= maxReach:
                return -1
            # Reset steps to the number of steps to reach maxReach from the current index.
            step = maxReach - i

    return -1

# Example Usage:

# Example 1:
arr1 = [2, 3, 1, 1, 4]
print("Minimum jumps for", arr1, ":", min_jumps(arr1))

# Example 2:
arr2 = [1, 1, 0, 1]
print("Minimum jumps for", arr2, ":", min_jumps(arr2))

Conclusion

This tutorial presented a greedy algorithm to determine the minimum number of jumps needed to reach the end of an array. The approach efficiently calculates the answer in O(n) time and O(1) space, making it ideal for DSA interviews.