# Easy Java Solution using Priority Queue and Comparator (18ms)

• This is a very similar approach to solving the sliding window problem (maximum sliding window), where we use a priority queue to keep things ordered.

We use a Comparator function that implements the `compare` method, which is called by the Priority Queue when a new number is added. This allows us to modify the default behavior of comparing integers in natural order (i.e ascending)

I decided to share a solution since I seen only a few somewhat similar methods of solving. Plus I wanted to offer some explanation.

The run time of this will ne O(n + k), since we have to iterate though the entire array of integers, and then remove k-1 largest elements. The priority queue allows for log (k) insertions. Do correct me if I am wrong.

Note for the newer Java users, the weird function inside a function syntax you see isn't too complicated. We're basically writing an anonymous function (function without a name) nested inside a `Comparator()` object, since one of the requirements of `Comparator` is to implement `public int compare(T a, T b)`. (It is an abstract method that must be implemented else the Java compiler will not allow you to proceed.

``````public class Solution {
public int findKthLargest(int[] nums, int k) {
int len = nums.length;
// if(len == 0) return 0; //we get to assume k is always valid
Queue<Integer> pq = new PriorityQueue(nums.length,
new Comparator<Integer>(){
public int compare(Integer a, Integer b) {
return Integer.compare(b, a);
}
});
for(int num : nums)
pq.offer(num);

int kth = 0;
for(int i = 0; i < k; i++)
kth = pq.poll();

return kth;
}
}``````

• You can just use the normal order. and keep the queue's size under k by polling out the min when exceed, then the front of the queue will always be the kth largest element;

``````   public class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue(k+1);
for (int i : nums) {
minHeap.offer(i);
if (minHeap.size() > k) minHeap.poll();
}
return minHeap.poll();
}
}``````

• Since we are removing elements from the heap the moment the size exceeds k (as done by minHeap.size() > k), is it necessary to create that heap with a size of k+1 ?

I created a normal heap and it passed OJ -
public int findKthLargest(int[] nums, int k){
PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
for(int i = 0; i < nums.length; i++){
minHeap.offer(nums[i]);
if(minHeap.size() > k)
minHeap.poll();
}
return minHeap.poll();
}

PS: I apologize if the code doesn't come out properly edited. I am new here and don't know where to find the option of keeping the indentations in the code. Any help would be appreciated :)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.