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).

Example 1:

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

Example 2:

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

Example 3:

Input: nums = [2], k = 1
Output: 2

Constraints:

• 1 <= k <= nums.length <= 10^4
• -100 <= nums[i] <= 100

Solution Breakdown

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 [4,3,2,6,7,5], K=2: push 4,3 leaving [3,4]; push 2 then pop -> [3,4]; push 6 then pop 3 -> [4,6]; push 7 then pop 4 -> [6,7]; push 5 then pop 5 -> [6,7]. Root is 6, 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 [9,9,9,9] with K=2 correctly returns 9.

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.