Arrays: Program to find the kth largest element in the array

To find the kth largest element from a given array, we will use a data structure called heap - specifically min heap.
To understand more about heap data structure, refer the heap section.
We will create a min heap which will contain only top k highest elements, and at the top of the heap, it will contain the
smallest element among the k elements in the heap
 

How does it work?

We push all the array elements into the min heap. Once the number of elements in the min heap exceeds k, we will remove an element from the top.
Once all the elements have been processed from the array, the min heap will have k elements.
Those k elements will be the k largest elements of the array that are left in the min heap.
And we can find our element by fetching the top element which will be the kth largest element.

Algorithm

1. Create a Min Heap named minHeap
2. For num in nums do:
   • If (size of minHeap < k) OR (num > top element of minHeap): add num to heap
   • If the size of minHeap > k: remove top element from heap
3. Return the top element of the minHeap

Complexity

Time Complexity: O(N * LogK)
Space Complexity: O(K)

The Time Complexity is O(N * LogK) as we are looping through every element of the array and pushing the element in the heap
which has a max size of k elements and takes O(LogK) to push the element in the heap. The Space Complexity is O(K) because
of the minHeap which contains at most k elements.

Java Code

    import java.util.PriorityQueue;

    class KthLargestElement{
        
        public static int getKthLargestElement(int k, int nums[]) {
            
            // Creating a min heap using the inbuilt java class
            PriorityQueue minHeap = new PriorityQueue();
    
            for (int i = 0; i < nums.length; i++) {
    
                // Add the current num to the minHeap if:
                // 1. Number of elements in the heap is less than k
                // 2. current num is greater than the top of the heap
                if (minHeap.size() < k || nums[i] > minHeap.peek()) {
                    minHeap.add(nums[i]);
                }
    
                // Keeping the size of minHeap equal to k elements
                if (minHeap.size() > k) {
                    minHeap.poll();
                }
            }
    
            // Return the top elements, as it will be the kth largest element
            return minHeap.peek();
        }
    
        public static void main(String[] args) {
            int[] nums = { 8, 2, 6, 12, 11, 10 };
            int k = 3;
    
            System.out.println("The kth [" + k + "] largest number in nums is: " + 
               getKthLargestElement(k, nums));
        }
    
    }

Output

The kth [3] largest number in nums is: 10