# Java solution with O(n + k*log(n)) complexity

• Could not use Python due the lack of oob max-heap, enter Java.

Could not use Python due the lack of oob max-heap, enter Java.

Idea is to put everything into a max-heap (which is O(n)), and then just
pull the k-1 largest elements first, in order to return the k-th we need.
Pulling takes O(log(n)), hence the total complexity of O(n + k*log(n)). I
think that such can be simplified to just O(n) if n >> k.

``````import java.util.*;

class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> minHeap =
new PriorityQueue<>(nums.length, Collections.reverseOrder());
for(Integer x: nums) {
}
for(int i=0; i<k-1; i++) {
minHeap.poll();
}
return minHeap.poll();
}
}
``````

• hich is

Isn't adding to the queue O(n log n)? You have to do it once for each array element (n), but adding an array element to a java priority queue is O(log n). So overall it's O(n log(n) k log(n)).

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