Minimum number of Jumps required to reach the end

Given an array of integers where each element represents the maximum number of steps that can be made forward from that element, find the minimum number of jumps required to reach the end of the array, starting from the first element. If it is not possible to reach the end, return -1.

Input/Output Examples

plaintext
Example 1:
Input: arr = [2, 3, 1, 1, 4]
Output: 2
Explanation: The minimum number of jumps to reach the end is 2:
Jump from index 0 to index 1, then jump to the last index.

Example 2:
Input: arr = [1, 1, 1, 1, 1]
Output: 4
Explanation: You need 4 jumps to reach the last index, jumping one step each time.

Example 3:
Input: arr = [1, 3, 6, 1, 0, 9]
Output: 3
Explanation: The minimum number of jumps to reach the end is 3:
Jump from index 0 to index 1, then to index 2, then jump directly to the last index.

Approach to find the Minimum number of Jumps

  1. Dynamic Programming Approach:
    • Use a dp array where dp[i] represents the minimum number of jumps required to reach index i.
    • Initialize dp[0] = 0 (since no jump is required to stay at the start) and dp[i] = ∞ for all other indices.
    • For each index i, check the reachable indices from i (i.e., i + 1 to i + arr[i]). For each reachable index j, update dp[j] = min(dp[j], dp[i] + 1) to store the minimum number of jumps to reach index j.
  2. Algorithm:
    • Initialize a DP array with ∞ and set dp[0] = 0.
    • Traverse through the array, and for each element arr[i], update the DP array for all reachable positions from i.
    • The final answer will be stored in dp[n-1] (the last index).
    • If the value in dp[n-1] is still ∞, return -1 since it's not possible to reach the end.
  3. Edge Cases:
    • If the array has only one element, no jumps are needed.
    • If the first element is 0 and n > 1, it’s impossible to reach the end, so return -1.

C++ Program to find the Minimum Number of Jumps

cpp
#include <iostream>
#include <vector>
#include <climits>
using namespace std;

// Function to find the minimum number of jumps to reach the end of the array
int minJumps(vector<int>& arr) {
    int n = arr.size();
    if (n == 1) return 0; // No jumps needed if there's only one element
    if (arr[0] == 0) return -1; // Cannot jump anywhere if the first element is 0

    // Initialize a DP array with large values (infinity)
    vector<int> dp(n, INT_MAX);
    dp[0] = 0; // No jumps needed to reach the first element

    // Build the DP table
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j <= i + arr[i] && j < n; j++) {
            dp[j] = min(dp[j], dp[i] + 1);
        }
    }

    return dp[n - 1] == INT_MAX ? -1 : dp[n - 1];
}

int main() {
    vector<int> arr = {2, 3, 1, 1, 4};
    int result = minJumps(arr);
    
    cout << "Minimum number of jumps: " << result << endl;
    return 0;
}

Java Program to find the Minimum number of Jumps

java
import java.util.Arrays;

public class MinJumps {

    // Function to find the minimum number of jumps to reach the end of the array
    public static int minJumps(int[] arr) {
        int n = arr.length;
        if (n == 1) return 0; // No jumps needed if there's only one element
        if (arr[0] == 0) return -1; // Cannot jump anywhere if the first element is 0

        // Initialize a DP array with large values (infinity)
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0; // No jumps needed to reach the first element

        // Build the DP table
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j <= i + arr[i] && j < n; j++) {
                dp[j] = Math.min(dp[j], dp[i] + 1);
            }
        }

        return dp[n - 1] == Integer.MAX_VALUE ? -1 : dp[n - 1];
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 1, 1, 4};
        int result = minJumps(arr);

        System.out.println("Minimum number of jumps: " + result);
    }
}

Python Program to find the Minimum number of Jumps

python
# Function to find the minimum number of jumps to reach the end of the array
def min_jumps(arr):
    n = len(arr)
    if n == 1:
        return 0  # No jumps needed if there's only one element
    if arr[0] == 0:
        return -1  # Cannot jump anywhere if the first element is 0

    # Initialize a DP array with large values (infinity)
    dp = [float('inf')] * n
    dp[0] = 0  # No jumps needed to reach the first element

    # Build the DP table
    for i in range(n):
        for j in range(i + 1, min(i + arr[i] + 1, n)):
            dp[j] = min(dp[j], dp[i] + 1)

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

# Example usage
if __name__ == "__main__":
    arr = [2, 3, 1, 1, 4]
    result = min_jumps(arr)
    print("Minimum number of jumps:", result)

Time Complexity:

  • O(n²): The outer loop runs n times, and for each element, we may potentially iterate up to arr[i] elements in the inner loop.

Space Complexity:

  • O(n): We use a DP array of size n to store the minimum number of jumps required to reach each index.

DSA

2922

366

Related Articles