Minimum Jumps to Reach End 🎯

Welcome to this comprehensive guide on the Minimum Jumps to Reach End problem, a fascinating topic in the realm of Algorithms and Data Structures! This lesson is designed to help you understand this concept from the ground up, whether you're a beginner or an intermediate learner. Let's dive in!

Understanding the Problem 📝

The Minimum Jumps to Reach End problem is about finding the minimum number of jumps needed to reach the end of an array from any starting point. Each element in the array represents a distance to the next position.

python

# Example array
arr = [2, 3, 1, 1, 4]

In this example, if we start from the first position, we can jump 2 steps, then 3 steps, and finally 1 step to reach the end. The minimum number of jumps required is 2.

Brute Force Approach 💡

Before diving into the optimal solution, let's quickly discuss a brute force approach. This method checks all possible paths from the start and finds the one with the minimum number of jumps. However, it's not practical for large arrays due to its high time complexity.

python

def minJumpsBruteForce(arr):
    # Base case: if only one element, return 0
    if len(arr) == 1:
        return 0

    # Iterate through each index
    for i in range(len(arr) - 1):
        # Initialize the number of jumps and visited list
        jumps, visited = 0, set()

        # Try to find a path with the minimum number of jumps
        def findPath(current):
            # If visited or out of bounds, return -1
            if current >= len(arr) or current in visited:
                return -1

            # If at the end, return 0
            if current == len(arr) - 1:
                return 0

            # Mark the current index as visited
            visited.add(current)

            # Recursively try to find a path from the current index
            # Adding 1 to the current index because we've already moved to the next position
            result = max(arr[current] + findPath(current + arr[current] + 1), 0)

            # If we found a path, return it
            if result != -1:
                return result + 1

        # Find the path from the current index and update the minimum jumps
        result = findPath(i)
        if result != -1:
            jumps = min(jumps, result)

    # Return the minimum number of jumps
    return jumps

Optimal Approach 💡

The optimal approach uses dynamic programming to find the minimum number of jumps efficiently. It calculates the minimum number of jumps needed from each index, considering the possibility to jump 1, 2, or 3 steps ahead.

python

def minJumps(arr):
    # Initialize the number of jumps, reached indices, and the end index
    jumps, reached, end = 0, set([0]), len(arr) - 1

    while len(reached) < end:
        new_reached = set()

        # Loop through the indices we've reached
        for i in reached:
            # If the current index is the end, we're done
            if i == end:
                return jumps

            # Add the current index to the new_reached set
            new_reached.add(i)

            # Check if we can jump 1, 2, or 3 steps ahead
            for k in range(1, 4):
                # Calculate the next index
                next = i + k

                # If the next index is within the array bounds and not already reached, update the new_reached set and jumps
                if next < len(arr) and next not in reached:
                    new_reached.add(next)
                    if next >= end:
                        return jumps + 1

        # Update the reached indices
        reached = new_reached
        jumps += 1

    return -1 📝 **Note:** If the loop finishes without finding a path to the end, it means that no path exists, and we return -1.

Minimum Jumps to Reach End 🎯

Minimum Jumps to Reach End 🎯

Understanding the Problem 📝

Brute Force Approach 💡

Optimal Approach 💡

Quiz 📝