Minimum jumps to reach end of the array with given conditions
Given an array A[], the task is to print the minimum number of jumps needed to reach the last element of A[] starting from the first element. If it is impossible to reach the last element print -1. A jump can be made from index i to j if all the below conditions are met:
- i < j
- A[i] >= A[j]
- There must be no elements between index i and j or all the elements in between index i and j, must be <= A[j]
Examples:
Input: N = 9, A[] = {20, 16, 13, 9, 17, 11, 15, 8, 7}
Output: 4
Explanation: The jumps will be 20 →17 → 15 → 8 → 7.
- First jump: Let us take i = 0 and j = 4. Then (A[0] = 20) >= (A[4] = 17) and all the elements between both indices are less than or equal to 17. Thus it is a valid jump.
- Second jump: Let us take i = 4 and j = 6. Then (A[4] = 17) >= (A[6] = 15) and all the elements between both indices are less than or equal to 15. Thus it is a valid jump.
- Third jump: Let us take i = 6 and j = 7. Then (A[6] = 15) >= (A[7] = 8) and there are no elements between them. Thus, it is a valid jump.
- Fourth jump: Let us take the i = 7 and j = 8. Then (A[7] = 8) >= (A[8] = 7) and there are no elements between them. Thus, it is a valid jump.
Input: N = 4, A[] = {20, 23, 34, 56}
Output: -1
Explanation: It can be verified that it is impossible to reach the last element of A[], therefore output is -1.
Approach: Implement the idea below to solve the problem
The problem is based on the Greedy Approach. If we observe the above conditions, then larger the value at any index i, more are the number of options to jump to the next element. So, If we are currently at any index i, then the most optimal jump would be to the index j such that j is farthest from i and there is no element after j which is greater than or equal to A[j] and less than A[i] because if there is an element after j which lies in range [A[i]+1, A[j]], then we will jump to that element rather than j as it is closer to the last element and we have a larger value which means we will more options to jump to the next element.
Steps to solve the problem:
- Declare two variables let say Max = -1 and Count = 0 to keep track of the maximum element and count the number of jumps respectively.
- Run a loop from i = (N – 1) to i > 0 and follow below mentioned steps under the scope of loop:
- If (A[i] > Max)
- Max = A[i]
- Count++
- If (A[i] > Max)
- If (A[0] < Max)
- Count = -1
- Output the value of Count.
Below is the implementation of the approach:
C++
#include <iostream> using namespace std; void min_jumps( int N, int A[]) { int max = -1, count = 0; for ( int i = N - 1; i > 0; i--) { if (A[i] > max) { max = A[i]; count++; } } if (A[0] < max) count = -1; cout << count << endl; } int main() { int N = 9; int A[] = {20, 16, 13, 9, 17, 11, 15, 8, 7}; min_jumps(N, A); return 0; } |
Java
// Java code to implement the approach import java.util.*; class GFG { // Driver Class public static void main(String[] args) throws java.lang.Exception { // Inputs int N = 9 ; int A[] = { 20 , 16 , 13 , 9 , 17 , 11 , 15 , 8 , 7 }; // Function call min_jumps(N, A); } public static void min_jumps( int N, int A[]) { // Variable to store the maximum element // and the number of jumps int max = - 1 , count = 0 ; for ( int i = N - 1 ; i > 0 ; i--) { if (A[i] > max) { max = A[i]; count++; } } // If it is impossible to reach // the last element if (A[ 0 ] < max) count = - 1 ; // Printing the minimum number // of operations System.out.println(count); } } |
Python
# Function to calculate the minimum number of jumps required def min_jumps(N, A): max_val = - 1 # Initialize the maximum value to -1 count = 0 # Initialize the jump count to 0 # Iterate through the array in reverse order for i in range (N - 1 , 0 , - 1 ): if A[i] > max_val: max_val = A[i] # Update the maximum value count + = 1 # Increment the jump count # Check if it's impossible to reach the first element if A[ 0 ] < max_val: count = - 1 # Set count to -1 to indicate it's not possible to reach print (count) # Main function def main(): N = 9 A = [ 20 , 16 , 13 , 9 , 17 , 11 , 15 , 8 , 7 ] # Call the min_jumps function to find the minimum jumps min_jumps(N, A) if __name__ = = "__main__" : main() |
C#
// C# code to implement the above approach using System; public class GFG { static void MinJumps( int N, int [] A) { // Variable to store the maximum element // and the number of jumps int max = -1, count = 0; for ( int i = N - 1; i > 0; i--) { if (A[i] > max) { max = A[i]; count++; } } // If it is impossible to reach // the last element if (A[0] < max) count = -1; // Printing the minimum number // of operations Console.WriteLine(count); } static void Main() { // Inputs int N = 9; int [] A = { 20, 16, 13, 9, 17, 11, 15, 8, 7 }; // Function call MinJumps(N, A); } } |
Javascript
// JavaScript code to implement the approach // Function to find the minimum number // of jumps required function minJumps(N, A) { let max = -1; let count = 0; // Traverse the array from right // to left for (let i = N - 1; i > 0; i--) { if (A[i] > max) { max = A[i]; count++; } } if (A[0] < max) count = -1; console.log(count); } // Driver Code const N = 9; const A = [20, 16, 13, 9, 17, 11, 15, 8, 7]; minJumps(N, A); |
4
Time Complexity: O(N), where N is the size of input array.
Auxiliary Space: O(1)