70. Kth Largest Element in an Array

Topic :

priority queue

Difficulty :

medium

Problem Link :

link

problem statement

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

You must solve it in O(n) time complexity.

Example 1:

Input: nums = [3,2,1,5,6,4], k = 2
Output: 5

Example 2:

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4

Constraints:

1 <= k <= nums.length <= 105
-104 <= nums[i] <= 104

solution

import java.io.*;
import java.util.*;
 class Kth_Largest_Element_in_an_Array
{
    public static void main(String args[]){
      int[]nums = {3,2,1,5,6,4};
      int k = 2;
      System.out.println("Kth-Largest Element is "+findKthLargest(nums,k));
    }
     static int findKthLargest(int[] nums, int k) {
      //make a priority queue of size K
      // make sure only K largest elements are present in the queue
      // since it is a min heap
      // the Kth largest element will be the smallest among the K largest elements
      // hence it will be at the top of the heap
     PriorityQueue<Integer> pq=new PriorityQueue<>();
     for(int i =0;i<k;i++) // insert the first k elements
      pq.add(nums[i]);
   
        for(int i=k;i<nums.length;i++) // for rest of the elements
        {
            if(pq.peek()<nums[i]) // if the element is greater than the top of the heap
            { pq.poll(); // remove the topmost element
             pq.add(nums[i]); // add the curr element
             }
            
      }
        return pq.peek(); // top of the priority queue will have the answer
    }
}