Given an array arr[] consisting of N integers and three integers X, Y, and K, the task is to find the farthest index that can be reached by the following operations:
- If arr[i] ? arr[i + 1]: Move from index i to i + 1.
- If arr[i] < arr[i+1]: Either decrement X by 1 if the value of X > 0 or decrement Y by (arr[i + 1] – arr[i]) if the value of Y > (arr[i+1] – arr[i]).
Examples:
Input: arr[] = {4, 2, 7, 6, 9, 14, 12}, X = 1, Y = 5, K = 0
Output: 4
Explanation:
Initially, K = 0.
arr[0] > arr[1]: Therefore, move to index 1.
arr[1] < arr[2]: Decrement X by 1 and move to index 2. Now X = 0.
arr[2] > arr[3]: Move to index 3.
arr[3] < arr[4]: Decrement Y by 3 and move to index 4. Now Y = 2
arr[4] < arr[5]: Neither X > 0 nor Y > 5. Hence, it is not possible to move to the next index.
Therefore, the maximum index that can be reached is 4.Input: arr[] = {14, 3, 19, 3}, X = 17, Y = 0, K = 1
Output: 3
Approach: The idea is to use X for the maximum difference between indexes and Y for the remaining difference. Follow the steps below to solve this problem:
- Declare a priority queue.
- Traverse the given array arr[] and perform the following operations:
- If the current element (arr[i]) is greater than the next element (arr[i + 1]), then move to the next index.
- Otherwise, push the difference of (arr[i + 1] – arr[i]) into the priority queue.
- If the size of the priority queue is greater than Y, then decrement X by the top element of the priority queue and pop that element.
- If X is less than 0, the farthest index that can be reached is i.
- After completing the above steps, if the value of X is at least 0, then the farthest index that can be reached is (N – 1).
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the farthest index // that can be reached void farthestHill( int arr[], int X, int Y, int N, int K) { int i, diff; // Declare a priority queue priority_queue< int > pq; // Iterate the array for (i = K; i < N - 1; i++) { // If current element is // greater than the next element if (arr[i] >= arr[i + 1]) continue ; // Otherwise, store their difference diff = arr[i + 1] - arr[i]; // Push diff into pq pq.push(diff); // If size of pq exceeds Y if (pq.size() > Y) { // Decrease X by the // top element of pq X -= pq.top(); // Remove top of pq pq.pop(); } // If X is exhausted if (X < 0) { // Current index is the // farthest possible cout << i; return ; } } // Print N-1 as farthest index cout << N - 1; } // Driver Code int main() { int arr[] = { 4, 2, 7, 6, 9, 14, 12 }; int X = 5, Y = 1; int K = 0; int N = sizeof (arr) / sizeof (arr[0]); // Function Call farthestHill(arr, X, Y, N, K); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to find the farthest index // that can be reached public static void farthestHill( int arr[], int X, int Y, int N, int K) { int i, diff; // Declare a priority queue PriorityQueue<Integer> pq = new PriorityQueue<Integer>(); // Iterate the array for (i = K; i < N - 1 ; i++) { // If current element is // greater than the next element if (arr[i] >= arr[i + 1 ]) continue ; // Otherwise, store their difference diff = arr[i + 1 ] - arr[i]; // Push diff into pq pq.add(diff); // If size of pq exceeds Y if (pq.size() > Y) { // Decrease X by the // top element of pq X -= pq.peek(); // Remove top of pq pq.poll(); } // If X is exhausted if (X < 0 ) { // Current index is the // farthest possible System.out.print(i); return ; } } // Print N-1 as farthest index System.out.print(N - 1 ); } // Driver code public static void main(String[] args) { int arr[] = { 4 , 2 , 7 , 6 , 9 , 14 , 12 }; int X = 5 , Y = 1 ; int K = 0 ; int N = arr.length; // Function Call farthestHill(arr, X, Y, N, K); } } // This code is contributed by divyeshrabadiya07 |
Python3
# Python3 program for the above approach # Function to find the farthest index # that can be reached def farthestHill(arr, X, Y, N, K): # Declare a priority queue pq = [] # Iterate the array for i in range (K, N - 1 , 1 ): # If current element is # greater than the next element if (arr[i] > = arr[i + 1 ]): continue # Otherwise, store their difference diff = arr[i + 1 ] - arr[i] # Push diff into pq pq.append(diff) # If size of pq exceeds Y if ( len (pq) > Y): # Decrease X by the # top element of pq X - = pq[ - 1 ] # Remove top of pq pq[ - 1 ] # If X is exhausted if (X < 0 ): # Current index is the # farthest possible print (i) return # Print N-1 as farthest index print (N - 1 ) # Driver Code arr = [ 4 , 2 , 7 , 6 , 9 , 14 , 12 ] X = 5 Y = 1 K = 0 N = len (arr) # Function Call farthestHill(arr, X, Y, N, K) # This code is contributed by code_hunt |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to find the farthest index // that can be reached public static void farthestHill( int [] arr, int X, int Y, int N, int K) { int i, diff; // Declare a priority queue List< int > pq = new List< int >(); // Iterate the array for (i = K; i < N - 1; i++) { // If current element is // greater than the next element if (arr[i] >= arr[i + 1]) continue ; // Otherwise, store their difference diff = arr[i + 1] - arr[i]; // Push diff into pq pq.Add(diff); pq.Sort(); pq.Reverse(); // If size of pq exceeds Y if (pq.Count > Y) { // Decrease X by the // top element of pq X -= pq[0]; // Remove top of pq pq.RemoveAt(0); } // If X is exhausted if (X < 0) { // Current index is the // farthest possible Console.Write(i); return ; } } // Print N-1 as farthest index Console.Write(N - 1); } // Driver code public static void Main(String[] args) { int [] arr = { 4, 2, 7, 6, 9, 14, 12 }; int X = 5, Y = 1; int K = 0; int N = arr.Length; // Function Call farthestHill(arr, X, Y, N, K); } } // This code is contributed by gauravrajput1 |
Javascript
<script> // Javascript program for the above approach // Function to find the farthest index // that can be reached function farthestHill(arr, X, Y, N, K) { var i, diff; // Declare a priority queue var pq = []; // Iterate the array for (i = K; i < N - 1; i++) { // If current element is // greater than the next element if (arr[i] >= arr[i + 1]) continue ; // Otherwise, store their difference diff = arr[i + 1] - arr[i]; // Push diff into pq pq.push(diff); pq.sort(); pq = pq.reverse(); // If size of pq exceeds Y if (pq.length > Y) { // Decrease X by the // top element of pq X -= pq[0]; // Remove top of pq pq = pq.slice(1); } // If X is exhausted if (X < 0) { // Current index is the // farthest possible document.write(i); return ; } } // Print N-1 as farthest index document.write(N - 1); } // Driver code var arr = [4, 2, 7, 6, 9, 14, 12]; var X = 5, Y = 1; var K = 0; var N = arr.length; // Function Call farthestHill(arr, X, Y, N, K); // This code is contributed by SURENDRA_GANGWAR. </script> |
4
Time Complexity: O(N*log(E)), where E is the maximum number of elements in the priority queue.
Auxiliary Space: O(E)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!