Given an array arr[] of size N and an integer K. The task is to find the Kth largest element from the right of every element in the array. If there are not enough elements to the right then print the same element.
Examples:
Input: N = 6, K = 3, arr[] = {4, 5, 3, 6, 7, 2}
Output: 5 3 2 6 7 2
Explanation: The elements right to 4 are {5, 3, 6, 7, 2}.
So 3rd largest element to the right of 4 is 5.
Similarly, repeat the process for the rest of the elements.
And 7 and 2 does not have sufficient element to the right.
So, they are kept as it is.Input: N = 5, K = 2, arr[] = {-4, 7, 5, 3, 0}
Output: 5 3 0 3 0
Naive Approach: The naive approach is to sort every subarray to the right of every element and check whether the Kth largest element exists or not. If it exists, print the Kth largest element, else print the same element.
Below is the implementation of the above approach:
C++14
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the Kth// largest element to the right// of every elementint getKLargest(int* arr, int r, int l, int& K){ // Elements to the right // of current element vector<int> v(arr, arr + l + 1); // There are greater than K elements // to the right if (l - r >= K) { // Sort the vector sort(v.begin() + r + 1, v.end()); return v[l - K + 1]; } else return v[r];}// Driver Codeint main(){ int arr[] = { -4, 7, 5, 3, 0 }; int N = sizeof(arr) / sizeof(arr[0]); int K = 2; for (int i = 0; i < N; i++) cout << getKLargest(arr, i, N - 1, K) << " "; return 0;} |
Java
// Java code for the above approachimport java.util.*;class GFG{ // Function to sort the elements of the array // from index a to index b static void sort(int[] arr, int N, int a, int b) { // Variables to store start and end of the index // range int l = Math.min(a, b); int r = Math.max(a, b); // Temporary array int[] temp = new int[r - l + 1]; int j = 0; for (int i = l; i <= r; i++) { temp[j] = arr[i]; j++; } // Sort the temporary array Arrays.sort(temp); // Modifying original array with temporary array // elements j = 0; for (int i = l; i <= r; i++) { arr[i] = temp[j]; j++; } } // Function to find the Kth // largest element to the right // of every element static int getKLargest(int[] arr, int r, int l, int K) { // Elements to the right // of current element int n = arr.length; int[] v = new int[l + 1]; for (int i = 0; i < l + 1; i++) { v[i] = arr[i]; } // There are greater than K elements // to the right if (l - r >= K) { // Sort the vector sort(v, n, r + 1, n - 1); return v[l - K + 1]; } else return v[r]; } // Driver Code public static void main(String[] args) { int arr[] = { -4, 7, 5, 3, 0 }; int N = arr.length; int K = 2; for (int i = 0; i < N; i++) System.out.print(getKLargest(arr, i, N - 1, K) + " "); }}// This code is contributed by code_hunt. |
Python3
# Python code for the above approach# Function to find the Kth# largest element to the right# of every elementdef getKLargest(arr, r, l, K): # Elements to the right # of current element v = arr[0: l + 1] # There are greater than K elements # to the right if (l - r >= K): # Sort the vector temp1 = v[0: r + 1] temp = v[r + 1:] temp.sort() v = temp1 + temp return v[l - K + 1] else: return v[r]# Driver Codearr = [-4, 7, 5, 3, 0]N = len(arr)K = 2for i in range(N): print(getKLargest(arr, i, N - 1, K), end=" ")# This code is contributed by Saurabh Jaiswal |
C#
// C# program for the above approachusing System;class GFG{ // Function to sort the elements of the array // from index a to index b static void sort(int[] arr, int N, int a, int b) { // Variables to store start and end of the index // range int l = Math.Min(a, b); int r = Math.Max(a, b); // Temporary array int[] temp = new int[r - l + 1]; int j = 0; for (int i = l; i <= r; i++) { temp[j] = arr[i]; j++; } // Sort the temporary array Array.Sort(temp); // Modifying original array with temporary array // elements j = 0; for (int i = l; i <= r; i++) { arr[i] = temp[j]; j++; } } // Function to find the Kth // largest element to the right // of every element static int getKLargest(int[] arr, int r, int l, int K) { // Elements to the right // of current element int n = arr.Length; int[] v = new int[l + 1]; for (int i = 0; i < l + 1; i++) { v[i] = arr[i]; } // There are greater than K elements // to the right if (l - r >= K) { // Sort the vector sort(v, n, r + 1, n - 1); return v[l - K + 1]; } else return v[r]; } // Driver Code public static void Main() { int[] arr = { -4, 7, 5, 3, 0 }; int N = arr.Length; int K = 2; for (int i = 0; i < N; i++) Console.Write(getKLargest(arr, i, N - 1, K) + " "); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Function to find the Kth // largest element to the right // of every element function getKLargest(arr, r, l, K) { // Elements to the right // of current element let v = arr.slice(0, l + 1); // There are greater than K elements // to the right if (l - r >= K) { // Sort the vector let temp1 = v.slice(0, r + 1); let temp = v.slice(r + 1); temp.sort(function (a, b) { return a - b }) v = temp1.concat(temp) return v[l - K + 1]; } else return v[r]; } // Driver Code let arr = [-4, 7, 5, 3, 0]; let N = arr.length; let K = 2; for (let i = 0; i < N; i++) document.write(getKLargest(arr, i, N - 1, K) + " ") // This code is contributed by Potta Lokesh </script> |
Output
5 3 0 3 0
Time Complexity: O(N2 * logN)
Auxiliary Space: O(N)
Approach based on Sets: Another approach is to use sets. Though both the approaches have same the time complexity, sets have an inbuilt sorting feature, it doesn’t require explicit sorting.
Below is the implementation of the above approach.
C++14
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the kth largest// element to the rightint getKLargest(vector<int>& arr, int r, int l, int& k){ set<int> s(arr.begin() + r + 1, arr.end()); if (l - r >= k) { set<int>::iterator it = s.end(); advance(it, -k); return *it; } else return arr[r];}// Driver codeint main(){ int arr[] = { -4, 7, 5, 3, 0 }; int N = sizeof(arr) / sizeof(arr[0]); int i, K = 2; vector<int> a(arr, arr + N); for (i = 0; i < N; i++) cout << getKLargest(a, i, N - 1, K) << " "; return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find the kth largest// element to the rightstatic int getKLargest(List<Integer> arr, int r, int l, int k){ HashSet<Integer> s = new HashSet<>(arr.subList(r+1,arr.size())); List<Integer> a = new ArrayList<>(s); if (l - r >= k) { return a.get(a.size()-k); } else return arr.get(r);}// Driver codepublic static void main(String[] args){ Integer arr[] = { -4, 7, 5, 3, 0 }; int N = arr.length; int i=0; int K = 2; List<Integer> a = Arrays.asList(arr); for (i = 0; i < N; i++) System.out.print(getKLargest(a, i, N - 1, K) + " ");}}// This code is contributed by shikhasingrajput |
Python3
# Python3 program for the above approach# def to find the kth largest# element to the rightdef getKLargest( arr , r , l , k): s = set() for i in range(r+1,len(arr)): s.add(arr[i]) a = [] for p in s: a.append(p) if(l - r >= k): return a[len(a)- k] else: return arr[r] # Driver code arr = [ -4, 7, 5, 3, 0 ]N = len(arr)i = 0K = 2a = arrfor i in range(N): print(getKLargest(a, i, N - 1, K) ,end=" ")# This code is contributed by shinjanpatra |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG{ // Function to find the kth largest // element to the right static int getKLargest(List<int> arr, int r, int l, int k) { HashSet<int> s = new HashSet<int>(arr.GetRange(r+1,arr.Count-(r+1))); List<int> a = new List<int>(s); a.Reverse(); if (l - r >= k) { return a[a.Count-k]; } else return arr[r]; } // Driver code public static void Main(String[] args) { int []arr = { -4, 7, 5, 3, 0 }; int N = arr.Length; int i=0; int K = 2; List<int> a = new List<int>(arr); for (i = 0; i < N; i++) Console.Write(getKLargest(a, i, N - 1, K) + " "); }}// This code is contributed by 29AjayKumar |
Javascript
<script>// javascript program for the above approach // Function to find the kth largest // element to the right function getKLargest( arr , r , l , k) { var s = new Set(); for(let i = r+1;i<arr.length;i++) s.add(arr[i]); // <>(arr.subList(r + 1, arr.size())); var a = []; for(let p of s) a.push(p); a.reverse(); if (l - r >= k) { return a[a.length - k]; } else return arr[r]; } // Driver code var arr = [ -4, 7, 5, 3, 0 ]; var N = arr.length; var i = 0; var K = 2; var a = (arr); for (var i = 0; i < N; i++) document.write(getKLargest(a, i, N - 1, K) + " ");// This code contributed by Rajput-Ji </script> |
Output
5 3 0 3 0
Time Complexity: O(N2 * logN)
Auxiliary Space: O(N)
Efficient Approach: The idea to efficiently solve the problem is:
Insert each element of the array in a vector and sort them in decreasing order. Then delete each element and print the Kth largest from the sorted vector.
Follow the steps mentioned below to implement the idea:
- First, insert all the elements in a vector.
- Sort the vector in decreasing order.
- Iterate through the array from i = 0 to N:
- Delete arr[i] from the vector.
- If there are at least K elements left, print the Kth largest from the vector.
- Otherwise, print the same element.
Below is the implementation of the above approach.
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// Function to print the Kth// largest element to the right// of every elementint getKLargest(int arr[], int n, int k){ // Storing elements in a vector vector<int> v(arr, arr + n ); // Sort the vector in decreasing order sort(v.begin(),v.end(),greater<int>()); // Iterating the for loop // to find kth largest element // for every element in the array for(int i=0;i<n;i++) { // Erase the current element from the vector v.erase(remove(v.begin(), v.end(), arr[i]), v.end()); // If kth largest element is possible // then print it. if(v.size()>=k) { cout<<v[k-1]<<" "; } // If kth largest is not possible then // print the element in the array. else { cout<<arr[i]<<" "; } }}// Driver Codeint main(){ int arr[] = { -4, 7, 5, 3, 0 }; int N = sizeof(arr) / sizeof(arr[0]); int K = 2; // Function call getKLargest(arr, N , K); return 0;}// This code is contributed by Pushpesh raj. |
Java
// Java code for the above approachimport java.util.*; class GFG { // Function to print the Kth // largest element to the right // of every element static void getKLargest(int arr[], int n, int k) { // Storing elements in a vector Vector<Integer> v = new Vector<Integer>(); for (int i = 0; i < n; i++) v.add(arr[i]); // Sort the vector in decreasing order Collections.sort(v, Collections.reverseOrder()); // Iterating the for loop // to find kth largest element // for every element in the array for (int i = 0; i < n; i++) { // Erase the current element // from the vector v.remove(new Integer(arr[i])); // If kth largest element is possible // then print it. if (v.size() >= k) System.out.print(v.get(k - 1) + " "); // If kth largest is not // possible then print the // element in the array else System.out.print(arr[i] + " "); } } // Driver Code public static void main(String args[]) { int arr[] = { -4, 7, 5, 3, 0 }; int N = arr.length; int K = 2; // Function call getKLargest(arr, N , K); } }// This code is contributed by adityamaharshi21 |
Python3
# Python3 program for the above approach:## Function to print the Kth## largest element to the right## of every elementdef getKLargest(arr, n, k): ## Storing elements in a vector v = [] for i in arr: v.append(i) ## Sort the vector in decreasing order v.sort() v.reverse() ## Iterating the for loop ## to find kth largest element ## for every element in the array for i in range(n): ## Erase the current element from the vector v.remove(arr[i]) ## If kth largest element is possible ## then print it. if(len(v) >= k): print(v[k-1], end = ' ') ## If kth largest is not possible then ## print the element in the array. else: print(arr[i], end = ' ')## Driver codeif __name__=='__main__': arr = [-4, 7, 5, 3, 0] N = len(arr) K = 2 ## Function call getKLargest(arr, N , K) # This code is contributed by subhamgoyal2014. |
C#
// C# code for the above approachusing System;using System.Linq;// Function to print the Kth// largest element to the right// of every elementpublic class GFG { public static void getKLargest(int[] arr, int n, int k) { // Storing elements in a List var v = arr.ToList(); // Sort the List in decreasing order v.Sort((a, b) = > b - a); // Iterating the for loop // to find kth largest element // for every element in the array for (int i = 0; i < n; i++) { // Erase the current element from the List v.Remove(arr[i]); // If kth largest element is possible // then print it. if (v.Count >= k) { Console.Write(v[k - 1] + " "); } // If kth largest is not possible then // print the element in the array. else { Console.Write(arr[i] + " "); } } } // Driver Code public static void Main() { int[] arr = { -4, 7, 5, 3, 0 }; int N = arr.Length; int K = 2; // Function call getKLargest(arr, N, K); }} |
Javascript
<script>// JavaScript code for the above approach// Function to print the Kth// largest element to the right// of every elementfunction getKLargest(arr, n, k){ // Storing elements in a vector let v = arr.slice(); // Sort the vector in decreasing order v.sort((a,b)=>b-a); // Iterating the for loop // to find kth largest element // for every element in the array for(let i=0;i<n;i++) { // Erase the current element from the vector v.splice(v.indexOf(arr[i]),1); // If kth largest element is possible // then print it. if(v.length>=k) { document.write(v[k-1]," "); } // If kth largest is not possible then // print the element in the array. else { document.write(arr[i]," "); } }}// Driver Codelet arr = [ -4, 7, 5, 3, 0 ];let N = arr.length;let K = 2;// Function callgetKLargest(arr, N , K);// This code is contributed by shinjanpatra</script> |
Output
5 3 0 3 0
Time Complexity: O(N2)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
