Jump Game – Minimum Jumps to Reach End

Spread the love

Considering an array arr[] containing only non-negative numbers. Every member in the array shows the furthest forward jump that one may get from that element. This implies that we may leap any distance y such that y ≤ x if arr[i] = x. Starting from the first element, determine the fewest leaps needed to reach the array’s finish. We cannot pass through an element if its value is 0.

Note: Should we fall short of reaching the array’s end, return -1.

Table of Contents

Examples

Input: arr[] = [1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9]
Output: 3 (1-> 3 -> 9 -> 9)
Explanation: Jump from 1st element to 2nd element as there is only 1 step.
Now there are three options 5, 8 or 9. If 8 or 9 is chosen then the end node 9 can be reached. So 3 jumps are made.


Input:  arr[] = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Output: 10
Explanation: In every step a jump is needed so the count of jumps is 10.

Table of Content

Using Recursion – O(n^n) Time and O(n) Space
Using Top-Down DP (Memoization) – O(n^2) Time and O(n) Space

Using Recursion – O(n^n) Time and O(n) Space

C++

// c++ program to find the minimum number
// of jumps to reach the end of the array
#include <bits/stdc++.h>
using namespace std;

int minJumpsRecur(int i, vector<int> &arr) {
    
    // Return 0 when last element is reached.
    if (i >= arr.size()-1)
        return 0;

    // Traverse through all the points
    // reachable from arr[i].
    // Recursively, get the minimum number
    // of jumps needed to reach array end from
    // these points.
    int ans = INT_MAX;
    for (int j=i+1; j<=i+arr[i]; j++) {
        int val = minJumpsRecur(j, arr);
        if (val != INT_MAX)
            ans = min(ans, 1+val);
    }

    return ans;
}

// Function to return the minimum number
// of jumps to reach arr[h] from arr[l]
int minJumps(vector<int>& arr) {

    int ans =  minJumpsRecur(0, arr);
    
    // If end cannot be reached.
    if (ans == INT_MAX) 
        return -1;
        
    return ans;
}

int main() {
    vector<int> arr = { 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9 };
    cout << minJumps(arr);
    return 0;
}

Java

// Java program to find the minimum number
// of jumps to reach the end of the array

import java.util.Arrays;

class GfG {

    static int minJumpsRecur(int i, int[] arr) {
        
        // Return 0 when last element is reached.
        if (i >= arr.length - 1)
            return 0;

        // Traverse through all the points
        // reachable from arr[i].
        // Recursively, get the minimum number
        // of jumps needed to reach array end from
        // these points.
        int ans = Integer.MAX_VALUE;
        for (int j = i + 1; j <= i + arr[i]; j++) {
            int val = minJumpsRecur(j, arr);
            if (val != Integer.MAX_VALUE)
                ans = Math.min(ans, 1 + val);
        }

        return ans;
    }

    static int minJumps(int[] arr) {

        int ans = minJumpsRecur(0, arr);
        
        // If end cannot be reached.
        if (ans == Integer.MAX_VALUE) 
            return -1;
            
        return ans;
    }

    public static void main(String[] args) {
        int[] arr = { 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9 };
        System.out.println(minJumps(arr));
    }
}

Python

# Python program to find the minimum number
# of jumps to reach the end of the array

import sys

def minJumpsRecur(i, arr):
    
    # Return 0 when last element is reached.
    if i >= len(arr) - 1:
        return 0

    # Traverse through all the points
    # reachable from arr[i].
    # Recursively, get the minimum number
    # of jumps needed to reach array end from
    # these points.
    ans = sys.maxsize
    for j in range(i + 1, i + arr[i] + 1):
        val = minJumpsRecur(j, arr)
        if val != sys.maxsize:
            ans = min(ans, 1 + val)

    return ans

def minJumps(arr):
    ans = minJumpsRecur(0, arr)
    
    # If end cannot be reached.
    if ans == sys.maxsize:
        return -1
        
    return ans

if __name__ == "__main__":
    arr = [1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9]
    print(minJumps(arr))

C#

// C# program to find the minimum number
// of jumps to reach the end of the array

using System;

class GfG {

    static int minJumpsRecur(int i, int[] arr) {
        
        // Return 0 when last element is reached.
        if (i >= arr.Length - 1)
            return 0;

        // Traverse through all the points
        // reachable from arr[i].
        // Recursively, get the minimum number
        // of jumps needed to reach array end from
        // these points.
        int ans = int.MaxValue;
        for (int j = i + 1; j <= i + arr[i]; j++) {
            int val = minJumpsRecur(j, arr);
            if (val != int.MaxValue)
                ans = Math.Min(ans, 1 + val);
        }

        return ans;
    }

    static int minJumps(int[] arr) {

        int ans = minJumpsRecur(0, arr);
        
        // If end cannot be reached.
        if (ans == int.MaxValue) 
            return -1;
            
        return ans;
    }

    static void Main() {
        int[] arr = { 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9 };
        Console.WriteLine(minJumps(arr));
    }
}

JavaScript

// JavaScript program to find the minimum number
// of jumps to reach the end of the array

function minJumpsRecur(i, arr) {
    
    // Return 0 when last element is reached.
    if (i >= arr.length - 1)
        return 0;

    // Traverse through all the points
    // reachable from arr[i].
    // Recursively, get the minimum number
    // of jumps needed to reach array end from
    // these points.
    let ans = Infinity;
    for (let j = i + 1; j <= i + arr[i]; j++) {
        let val = minJumpsRecur(j, arr);
        if (val != Infinity)
            ans = Math.min(ans, 1 + val);
    }

    return ans;
}

function minJumps(arr) {
    let ans = minJumpsRecur(0, arr);
    
    // If end cannot be reached.
    if (ans == Infinity) 
        return -1;
        
    return ans;
}

let arr = [1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9];
console.log(minJumps(arr));

Output