You are given an array consisting of 'N' distinct positive integers and a number 'K'. Your task is to find the kth largest element in the array.
Example:
Consider the array {2,1,5,6,3,8} and 'K' = 3, the sorted array will be {8, 6, 5, 3, 2, 1}, and the 3rd largest element will be 5.
1) Kth largest element in an array is the kth element of the array when sorted in non-increasing order.
2) All the elements of the array are pairwise distinct.
The first line of the input contains an integer 'T' denoting the number of test cases.
The first line of each test case contains two space- separated integers 'N' and 'K', as described in the problem statement.
The second line of each test case contains 'N' space-separated integers, representing the elements of the array.
For each test case, print a single integer denoting the kth largest number in the given array.
You do not need to print anything, it has already been taken care of. Just implement the given function.
1 <= T <= 100
1 <= N <= 10^4
1 <= ARR[i] <= 10^9
1 <= K <= N
Time Limit: 1 sec
1
3 1
1 2 3
3
3 is the first largest element in the array {1,2,3}.
1
4 2
5 6 7 8
7
7 is the second largest element in the array {5,6,7,8}.
Sort the array.
O( N * log(N) ), where ‘N’ is the size of the array.
We can sort an array in O(N * log(N)).
O(1).
No extra space is used.
All tags
Sort by
Interview problems
Easy Java Solution
import java.util.* ;
import java.io.*;
public class Solution {
static int kthLargest(ArrayList<Integer> arr, int size, int K) {
// Write your code here.
PriorityQueue<Integer>q=new PriorityQueue<>();
for(int num:arr){
q.add(num);
if(q.size()>K) q.poll();
}
return q.peek();
}
}
Interview problems
JAVA SOLUTION || Kth largest element in the unsorted array ||
import java.util.* ;
import java.io.*;
public class Solution {
static int kthLargest(ArrayList<Integer> arr, int size, int K) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
for(int i : arr)pq.add(i);
while(pq.size() > K)pq.remove();
return pq.peek();
}
}
Interview problems
c++ solution
#include <bits/stdc++.h>
int kthLargest(vector<int>& arr, int size, int K)
{
sort(arr.begin(), arr.end());
K = size-K;
return arr[K];
}
Interview problems
check this c++ soln
#include <bits/stdc++.h>
int kthLargest(vector<int>& arr, int size, int K)
{
// Write your code here.
priority_queue<int> pq;
for (int i = 0; i < size; i++) {
pq.push(arr[i]);
}
while (K != 1) {
pq.pop();
K--;
}
return pq.top();
}
Interview problems
Easy solution in c++
#include <bits/stdc++.h>
int kthLargest(vector<int>& arr, int size, int K)
{
// Write your code here.
sort(arr.begin(),arr.end());
return arr[size-K];
}
Interview problems
Esay solution using Queue / CPP All the test case pass
#include <bits/stdc++.h>
int kthLargest(vector<int>& arr, int size, int K)
{
priority_queue<int>num;
for(int i=0; i<size; i++)
{
num.push(arr[i]);
}
while(K>1){
num.pop();
K--;
}
int p=num.top();
return p;
}
Interview problems
Kth largest element in the unsorted array || Simple Solution
#include <bits/stdc++.h>
int kthLargest(vector<int>& arr, int size, int K)
{
// Write your code here.
priority_queue<int> pq;
for(int i=0;i<size;i++){
pq.push(arr[i]);
}
while(K>1){
pq.pop();
K--;
}
int t=pq.top();
return t;
}
Interview problems
java || min PriorityQueue
static int kthLargest(ArrayList<Integer> arr, int size, int K) {
//implementing min PriorityQueue;
PriorityQueue<Integer> pq=new PriorityQueue<>();
for(int i=0;i<arr.size();i++){
//inserting k element in min PriorityQueue;
if(i<K){
pq.add(arr.get(i));
}
//after that replacing all min with max element until we get all k max element;
else{
if(pq.peek()<arr.get(i)){
pq.poll();
pq.add(arr.get(i));
}
}
}
return pq.peek();
}
Interview problems
Kth largest element in the unsorted array:- Python Solution
def kthLargest(arr, size, k):
arr.sort()
return arr[size-k]Interview problems
Java Solution
import java.util.* ;
import java.io.*;
public class Solution {
static int kthLargest(ArrayList<Integer> arr, int size, int K) {
// Write your code here.
PriorityQueue<Integer> pq = new PriorityQueue<>();
for(int i : arr)pq.add(i);
while(pq.size() > K)pq.remove();
return pq.peek();
}
}
