PROBLEM DESCRIPTION
Given an array arr[] and an integer K where K is smaller than size of array, the task is to find the Kth smallest element in the given array. It is given that all array elements are distinct.
Note :- l and r denotes the starting and ending index of the array.
SOLUTION
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution{
public static int kthSmallest(int[] arr, int l, int r, int k)
{
// max heap
PriorityQueue<Integer> pq = new PriorityQueue<>( (a,b) -> b-a );
// loop through all the elements from l to r
for(int i=l; i<=r; i++){
// add to max heap
pq.add(arr[i]);
// if size of max heap is more than k, remove top most element
if(pq.size() > k)
pq.poll();
}
// at this point, top of the heap should have kth largest element
return pq.peek();
}
}