Kth Largest Element in an Array — Practice

Problem

Given an integer array nums and an integer k, return the kth largest element in the array (the kth largest in sorted order, not the kth distinct element).

Examples

Example 1

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

Output: 5

Explanation: Sorted descending: 6,5,4,3,2,1 — the 2nd largest is 5.

Constraints

•1 <= k <= nums.length <= 10^5

Hints

Hint 1

Sorting the whole array works but does more work than necessary — you only need to know ONE position's value.

Hint 2

A min-heap of size k, not a max-heap of the whole array, is the efficient approach — think about why the heap should hold the k LARGEST seen so far, with the smallest of those at the top.

Hint 3

Once the heap has k elements, any new element smaller than the heap's top can be discarded immediately without ever entering the heap.

Solutions

public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // min-heap: smallest of the top-k sits at the top
    for (int n : nums) {
        minHeap.offer(n);
        if (minHeap.size() > k) minHeap.poll(); // discard the smallest — it can't be in the top k anymore
    }
    return minHeap.peek(); // the smallest element remaining IS the kth largest overall
}

Time: O(n log k) · Space: O(k)