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

As I had done the problem before, I knew the solution which involves dynamic programming as mentioned in the Geeksforgeeks link.

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).

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;
}

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

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;

    }

}

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 MathWorks EDG Associate interview questions & answers

Top HR questions asked in MathWorks EDG Associate