Minimum Jumps

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
186 upvotes
Asked in companies
DirectiMorgan StanleyAdobe

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
2
5
2 1 3 2 4
3
3 2 1
Sample Output 1:
2
1
Explanation For Sample Input 1:
In the 1st test case, Bobs jumps from shop 0 to shop 2 and then jumps from shop 2 to shop 4, so he needs two jumps to reach the last shop.

In the 2nd test case, Bobs jumps from shop 0 to shop 2, so he needs only one jump to reach the last shop.
Sample Input 2:
2
5
1 0 3 2 1
4
1 1 1 1
Sample Output 2:
-1
3
Hint

Think of a recursive approach to solve the problem.

Approaches (4)
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’.
Time Complexity

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

Space Complexity

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

O(N) recursion stack space will be used.

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Minimum Jumps
Full screen
Console