Sweaty Imposter

Kth Largest Element in an Array

MediumTop K ElementsBlind 75MidOpen on LeetCodeUpdated

You're given an unsorted integer array nums and an integer k. Return the k-th largest element: the value that would sit at position k (1-indexed) if nums were sorted from largest to smallest. Repeated values each take their own position, so this is not the k-th largest distinct value. Can you solve it without sorting the whole array?

Examples

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

Sorted from largest to smallest the array is [6,5,4,3,2,1], and the value in position 2 is 5.

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

Sorted from largest to smallest it is [6,5,5,4,3,3,2,2,1]. The two 5s fill positions 2 and 3, so position 4 holds 4.

Constraints

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

Hints

Hint 1

What's the smallest collection you can keep around that always contains the kth largest so far?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

Keep a min-heap of the k largest values seen so far. Push each number, and whenever the heap grows past k, pop its smallest element, which can't be among the top k. After the scan the heap holds exactly the k largest values, and its root, the smallest of them, is the k-th largest. O(n log k) time, O(k) space.

Time

O(n log k)

Space

O(k)

Pitfall

Removing duplicates first: repeated values count separately, so in the second example the answer is 4, not 3. Also pop only once the heap size exceeds k; popping when it reaches k leaves you holding the top k - 1.

Solutions

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int num : nums) {
            heap.offer(num);
            if (heap.size() > k) heap.poll();
        }
        return heap.peek();
    }
}
Drill This