Posts Kth smallest element (geeksforgeeks - SDE Sheet)
Post
Cancel

Kth smallest element (geeksforgeeks - SDE Sheet)

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.

geeksforgeeks

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();

    }
}
This post is licensed under CC BY 4.0 by the author.