Minimum Jumps
Bob lives with his wife in a city named Berland. Bob is a good husband, so he goes out with his wife every Friday to ‘Arcade’ mall.

‘Arcade’ is a very famous mall in Berland. It has a very unique transportation method between shops. Since the shops in the mall are laying in a straight line, you can jump on a very advanced trampoline from the shop i, and land in any shop between (i) to (i + Arr[i]), where Arr[i] is a constant given for each shop.

There are N shops in the mall, numbered from 0 to N-1. Bob's wife starts her shopping journey from shop 0 and ends it in shop N-1. As the mall is very crowded on Fridays, unfortunately, Bob gets lost from his wife. So he wants to know, what is the minimum number of trampoline jumps from shop 0 he has to make in order to reach shop N-1 and see his wife again. If it is impossible to reach the last shop, return -1.

Input format :

The first line of input contains a single integer T, representing the number of test cases or queries to be run. Then the T test cases follow. The first line of each test case contains a positive integer N, which represents the number of shops. The next line contains 'N' single space-separated positive integers representing a constant given for each shop.

Output Format :

For each test case, print the minimum number of jumps or -1, if it is impossible to reach the last shop.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1

Question

Minimum Jumps

Bob lives with his wife in a city named Berland. Bob is a good husband, so he goes out with his wife every Friday to ‘Arcade’ mall.

‘Arcade’ is a very famous mall in Berland. It has a very unique transportation method between shops. Since the shops in the mall are laying in a straight line, you can jump on a very advanced trampoline from the shop i, and land in any shop between (i) to (i + Arr[i]), where Arr[i] is a constant given for each shop.

There are N shops in the mall, numbered from 0 to N-1. Bob's wife starts her shopping journey from shop 0 and ends it in shop N-1. As the mall is very crowded on Fridays, unfortunately, Bob gets lost from his wife. So he wants to know, what is the minimum number of trampoline jumps from shop 0 he has to make in order to reach shop N-1 and see his wife again. If it is impossible to reach the last shop, return -1.

Input format :

The first line of input contains a single integer T, representing the number of test cases or queries to be run. 

Then the T test cases follow.

The first line of each test case contains a positive integer N, which represents the number of shops.

The next line contains 'N' single space-separated positive integers representing a constant given for each shop.

Output Format :

For each test case, print the minimum number of jumps or -1, if it is impossible to reach the last shop.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= N <= 5 * 10^4
0 <= Arr[i] <= N
Where T is the number of test cases, N is the size of the array and Arr[i] is the ith element in the array.

Accepted Answer

It can be solved by using mathematics. If the height of wall is less than or equal to x, only one jump is required. Otherwise run a while loop while height is greater than x, and calculate the jumps required by updating the height to height of wall – (climb up-climb down).

Accepted Answer

Recursive Approach

We will recursively find the minimum number of jumps.

Algorithm:

Let’s say we have a recursive function ‘minimumJumpsHelper’ which will return the minimum number of jumps to reach the last shop.

Call the function: minimumJumpsHelper(i).
If i is equal to N-1, return 0.
Make a variable ‘ans’ that stores the minimum number of jumps needed to reach the last shop from the current shop.
- Initialize ‘ans’ with a maximum value (INT_MAX).
Iterate on the shops from (i + 1) to (i + Arr[i]) and update the answer, i.e., ans = min( ans, 1 + minimumJumpsHelper(j) ) (where j denotes the shop, where we jumped).
Return the ‘ans’.

Space Complexity: O(n)Explanation:

O(N), Where N is the number of shops.

O(N) recursion stack space will be used.

Time Complexity: O(n^n)Explanation:

O(N ^ N), Where N is the number of shops.

From each shop, there will be at most N recursive calls and there are a total of N number of shops (1 to N). Thus, the final time complexity is O(N ^ N).

Accepted Answer

Memoization

In the previous approach, we are recalculating the answer to reach the last shop from a shop. We can optimise it by storing the answer for the amount which we have calculated.

For example, if the given array is {2, 1, 3, 2, 4}:

We are recalculating the answer for shops {2, 3}.

So since there are overlapping solutions, we can store the solution which we have calculated. For this, we will make an array DP to store the answer.

DP[i] denotes the minimum number of jumps needed to reach the last shop from the ith shop.

Algorithm:

In a recursive state, if we know the answer for the ith shop, then we will directly return the answer.
Let’s say we have a recursive function ‘minimumJumpsHelper’ which will return the minimum number of jumps to reach the last shop.
- Make an array DP of size N, initialize it with -1.
- Call the function: minimumJumpsHelper(i).
  - If i is equal to N, return 0.
  - If DP[i] is not equal to -1, return DP[i]
  - Make a variable ‘ans’ that stores the minimum number of jumps needed to reach the last shop from the current shop.
    - Initialize ‘ans’ with a maximum value (INT_MAX).
  - Iterate on the shops from (i + 1) to (i + Arr[i]) and update the answer, i.e., ans = min( ans, 1 + minimumJumpsHelper(j) ) (where j denotes the shop, where we jumped).
  - Update DP[i], DP[i] = ans.
  - Return the ‘ans’.

Space Complexity: O(n)Explanation:

O(N), Where N is the number of shops.

O(N) recursion stack space will be used, we are also making an array DP of size N which will take O(N) extra space. Thus, the final space complexity is O(N + N) = O(N).

Time Complexity: O(n^2)Explanation:

O(N ^ 2), Where N is the number of shops.

For each shop, we are iterating on the shops where we can jump from the current shop and there can be at most N shops. Thus, the final time complexity is O(N ^ 2).

C++ (g++ 5.4)

/*

    Time Complexity: O(N ^ 2)

    Space complexity: O(N)

    

    Where N is the number of shops.

*/



#include 



int minimumJumpsHelper(int i, vector &arr, int n, vector &dp)

{



    // Base case

    if (i == (n - 1))

    {

        return 0;

    }



    if (dp[i] != -1)

    {

        return dp[i];

    }



    // Initialize with a maximum value

    // Use long long to avoid overflow

    long long int ans = INT_MAX;



    for (int j = i + 1; j <= min(i + arr[i], n - 1); j++)

    {

        ans = min(ans, 1LL + minimumJumpsHelper(j, arr, n, dp));

    }



    dp[i] = ans;



    return ans;

}



int minimumJumps(vector &arr, int n)

{

    vector dp(n, -1);



    int ans = minimumJumpsHelper(0, arr, n, dp);



    if (ans == INT_MAX)

    {



        // Impossible to reach the last shop

        ans = -1;

    }

    return ans;

}

Python (3.5)

'''

    Time Complexity: O(N ^ 2)

    Space complexity: O(N)

    

    Where N is the number of shops.

'''



from sys import maxsize





def minimumJumpsHelper(i, arr, n, dp):



    # Base case

    if (i == (n - 1)):

        return 0



    if (dp[i] != -1):

        return dp[i]



    # Initialize with a maximum value

    ans = maxsize



    for j in range(i + 1, min(i + arr[i], n - 1) + 1):

        ans = min(ans, 1 + minimumJumpsHelper(j, arr, n, dp))



    dp[i] = ans

    return ans





def minimumJumps(arr, n):



    dp = [-1] * n



    ans = minimumJumpsHelper(0, arr, n, dp)



    if (ans == maxsize):

        

        # Impossible to reach the last shop

        ans = -1



    return ans

Java (SE 1.8)

/*

    Time Complexity: O(N ^ 2)

    Space complexity: O(N)

    

    Where N is the number of shops.

*/



import java.util.*;



public class Solution {

    public static int minimumJumpsHelper(int i, int[] arr, int n, int[] dp) {

        

        // Base case

        if (i == (n - 1)) {

            return 0;

        }



        if (dp[i] != -1) {

            return dp[i];

        }



        // Initialize with a maximum value

        // Use long long to avoid overflow

        long ans = Integer.MAX_VALUE;;



        for (int j = i + 1; j <= Math.min(i + arr[i], n - 1); j++) {

            ans = Math.min(ans, 1L + minimumJumpsHelper(j, arr, n, dp));

        }



        dp[i] = (int) ans;



        return (int) ans;

    }



    public static int minimumJumps(int[] arr, int N) {

        int[] dp = new int[N];

        Arrays.fill(dp, -1);



        int ans = minimumJumpsHelper(0, arr, N, dp);



        if (ans == Integer.MAX_VALUE) {

            

            // Impossible to reach the last shop

            ans = -1;

        }

        return ans;

    }

}

Accepted Answer

Tabulation

Make an array DP of size N to store the answer.

DP[i] denotes the minimum number of jumps needed to reach the last shop from the ith shop.

DP[N - 1] = 0.
Initialize all other values with a maximum value (INT_MAX).
Now iterate on shops from N - 2 to 1
- Let ‘i’ denote the current shop.
- Iterate on the shops where we can jump from the ith shop, i.e., from (i + 1) to (i + Arr[i]).
  - Update DP[i], DP[i] = min(DP[i] , 1 + DP[j]) (where j denotes the shop, where we jumped).
Return DP[0] as the answer.

Space Complexity: O(n)Explanation:

O(N), Where N is the number of shops.

We are making an array DP of size N which will take O(N) extra space. Thus, the final space complexity is O(N).

Time Complexity: O(n^2)Explanation:

O(N ^ 2), Where N is the number of shops.

For each shop, we are iterating on the shops where we can jump from the current shop and there can be at most N shops. Thus, the final time complexity is O(N ^ 2).

Python (3.5)

'''

    Time Complexity: O(N ^ 2)

    Space complexity: O(N)

    

    Where N is the number of shops.

'''



from sys import maxsize





def minimumJumps(arr, n):



    dp = [maxsize] * n



    dp[n - 1] = 0



    for i in range(n - 2, -1, -1):



        for j in range(i + 1, min(n - 1, i + arr[i]) + 1):



            if (dp[j] != maxsize):

                dp[i] = min(dp[i], 1 + dp[j])



    if (dp[0] == maxsize):



        # Impossible to reach the last shop

        return -1



    return dp[0]

C++ (g++ 5.4)

/*

    Time Complexity: O(N ^ 2)

    Space complexity: O(N)

    

    Where N is the number of shops.

*/



#include 



int minimumJumps(vector &arr, int n)

{

    vector dp(n, INT_MAX);



    dp[n - 1] = 0;



    for (int i = n - 2; i >= 0; i--)

    {

        for (int j = i + 1; j <= min(n - 1, i + arr[i]); j++)

        {

            if (dp[j] != INT_MAX)

            {

                dp[i] = min(dp[i], 1 + dp[j]);

            }

        }

    }



    if (dp[0] == INT_MAX)

    {



        // Impossible to reach the last shop

        return -1;

    }

    return dp[0];

}

Java (SE 1.8)

/*

    Time Complexity: O(N ^ 2)

    Space complexity: O(N)

    

    Where N is the number of shops.

*/



import java.util.Arrays;



public class Solution {

    public static int minimumJumps(int[] arr, int N) {

        int[] dp = new int[N];

        Arrays.fill(dp, Integer.MAX_VALUE);



        dp[N - 1] = 0;



        for (int i = N - 2; i >= 0; i--) {

            for (int j = i + 1; j <= Math.min(N - 1, i + arr[i]); j++) {

                if (dp[j] != Integer.MAX_VALUE) {

                    dp[i] = Math.min(dp[i], 1 + dp[j]);

                }

            }

        }



        if (dp[0] == Integer.MAX_VALUE) {

            

            // Impossible to reach the last shop

            return -1;

        }

        return dp[0];

    }

}

Accepted Answer

Linear Time Complexity

In this approach, we will calculate the farthest shop we can reach from shop 0 with x number of jumps.

For example, if the given array is {2, 3, 1, 2, 1} :

For x=1, we can reach shop 2 (shop 0 -> shop2).

For x=2, we can reach shop 4 (shop 0 -> shop1 -> shop 4)

Hence, we require a minimum two jumps to reach the last shop.

Algorithm:

Make three variables ‘maxReach’, ‘jumpsTaken’, and ‘stepsLeft’.
- ‘jumpsTaken’ denotes the number of jumps taken.
- ‘maxReach’ denotes the farthest shop we can reach with ‘jumpsTaken’ number of jumps.
- ‘stepsLeft’ denotes the number of steps we can still take (1 step means moving from shop i to shop (i + 1)).
Initialise variables:
- jumpsTaken = 1
- maxReach = Arr[0]
- stepsLeft = Arr[0]
Iterate on the shops from shop 1 to N - 2, let i denote the current shop.
- Update ‘maxReach’, maxReach = max(maxReach, i + Arr[i]).
- Decrement ‘stepsLeft’ by 1, stepsLeft = stepsLeft - 1.
- If stepsLeft is equal to 0:
  - Increment ‘jumpsTaken’ by 1, jumpsTaken = jumpsTaken + 1.
  - If i is greater than or equal to ‘maxReach’, then we cannot jump from shop i to any other shop, so we will return -1.
  - Else, stepsLeft = maxReach - i.
Return ‘jumpsTaken’.

Space Complexity: O(1)Explanation:

O(1)

Constant additional space is required.

Time Complexity: O(n)Explanation:

O(N), Where N is the number of shops.

We are traversing each shop exactly once. Thus, the final time complexity is O(N).

Java (SE 1.8)

/*

    Time Complexity: O(N)

    Space complexity: O(1)

    

    Where N is the number of shops.

*/



import java.util.Arrays;

public class Solution {

    public static int minimumJumps(int[] arr, int N) {

        if (N == 1) {

            return 0;

        }

        if (arr[0] == 0) {

            

            // We cannot jump from this shop

            return -1;

        }



        int jumpsTaken = 1;

        int maxReach = arr[0];

        int stepsLeft = arr[0];



        for (int i = 1; i <= (N - 2); i++) {

            maxReach = Math.max(maxReach, i + arr[i]);

            

            // We took a step to reach current index

            stepsLeft--;

            if (stepsLeft == 0) {

                jumpsTaken++;

                if (i >= maxReach) {

                    

                    // Impossible to reach the last shop

                    return -1;

                }

                stepsLeft = maxReach - i;

            }

        }

        return jumpsTaken;

    }

}

Python (3.5)

'''

    Time Complexity: O(N)

    Space complexity: O(1)

    

    Where N is the number of shops.

'''





def minimumJumps(arr, n):



    if (n == 1):

        return 0



    if (arr[0] == 0):

        # we cannot jump from this shop

        return -1



    jumpsTaken = 1

    maxReach = arr[0]

    stepsLeft = arr[0]



    for i in range(1, n - 1):



        maxReach = max(maxReach, i + arr[i])



        # we took a step to reach current index

        stepsLeft -= 1



        if (stepsLeft == 0):



            jumpsTaken += 1

            if (i >= maxReach):

                # Impossible to reach the last shop

                return -1



            stepsLeft = maxReach - i



    return jumpsTaken

C++ (g++ 5.4)

/*
    Time Complexity: O(N)
    Space complexity: O(1)
    
    Where N is the number of shops.
*/


int minimumJumps(vector &arr, int n)
{
    if (n == 1)
    {
        return 0;
    }
    if (arr[0] == 0)
    {
        // we cannot jump from this shop
        return -1;
    }

    int jumpsTaken = 1;
    int maxReach = arr[0];
    int stepsLeft = arr[0];

    for (int i = 1; i <= (n - 2); i++)
    {
        maxReach = max(maxReach, i + arr[i]);
        // we took a step to reach current index
        stepsLeft--;
        if (stepsLeft == 0)
        {
            jumpsTaken++;
            if (i >= maxReach)
            {
                // Impossible to reach the last shop
                return -1;
            }
            stepsLeft = maxReach - i;
        }
    }
    return jumpsTaken;
}

Bob lives with his wife in a city named Berland. Bob is a good husband, so he goes out with his wife every Friday to ‘Arcade’ mall.

Input format :

Output Format :

Note:

Constraints :

Top MakeMyTrip Software Developer interview questions & answers

Popular interview questions of Software Developer