LeetCode : 215. Kth Largest Element in an Array

[congr]

https://leetcode.com/problems/kth-largest-element-in-an-array/description/

[congr]

minHeap peek() can refer to Kth largest element.

similar to running median

[congr]

LeetCode AC Note that PriorityQueue's api is add/remove

Time complexity is O(K) + O((N-K) LogK)

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue();

        for (int i = 0; i<nums.length; i++) {
            if (minHeap.size() < k) minHeap.add(nums[i]);
            else {
                if (minHeap.peek() < nums[i]) {
                    minHeap.remove();
                    minHeap.add(nums[i]);
                }
            }
        }

        return (int)minHeap.peek();
    }
}

[congr]

It seems Quick select is better fit. https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/

https://leetcode.com/problems/kth-largest-element-in-an-array/discuss/60294/Solution-explained Quick select O(N) guaranteed running time + O(1) space