Kth Largest Element in an Array

Problem

Recommendation engines and leaderboard systems frequently need the Kth largest score from a list that is too large to sort. Finding it efficiently - without sorting the whole array - is the canonical heap warm-up. Return the Kth largest element in the integer array (not the Kth distinct element).

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

Solution

Approach: size-K min-heap (the top-K pattern).

Maintain a min-heap that never holds more than K elements. Walk the array once, pushing each value. After every push, if the heap has grown past K, pop the root - which is the current minimum. That pop discards an element too small to be among the K largest, so the heap always retains exactly the K largest values seen so far. The counter-intuitive part is the flavor: to keep the K largest you use a MIN-heap, because its root is the smallest of the survivors and is therefore the right element to evict the moment a bigger value arrives. Once the whole array is processed, the heap holds the K largest elements and its root min_heap[0] is the smallest of those K - which is precisely the Kth largest overall.

Trace [3,2,1,5,6,4], K=2: push 3,2 leaving [2,3]; push 1 then pop -> [2,3]; push 5 then pop 2 -> [3,5]; push 6 then pop 3 -> [5,6]; push 4 then pop 4 -> [5,6]. Root is 5, the 2nd largest.

Edge cases: K equal to the array length means no pop ever fires and the root is the array minimum (the Nth largest). Duplicates are counted by position, so [5,5,5,5] with K=2 correctly returns 5.

Complexity: O(n log K) time, O(K) space - each of n elements drives one O(log K) push/pop against a heap capped at K.