Solution: Kth Largest Element in an Array

Statement

Find the $k^{th}$ largest element in an unsorted array.

Note: We need to find the $k^{th}$ largest element in the sorted order, not the $k^{th}$ distinct element.

Constraints:

• $1 \leq$ k $\leq$ nums.length $\leq 10^3$

• $-10^4 \leq$ nums[i] $\leq 10^4$

Solution

The intuition behind using a min-heap is efficiently managing a subset of elements for the $k^{th}$​ largest position as the array is processed. Initially, the heap is filled with the first $k$ elements of the array, setting up an initial set of elements. As we iterate through the remaining elements, the algorithm evaluates each against the current smallest element (the root of the heap). If an element is larger, the top is removed, and the larger element is added to the heap, ensuring that the heap always contains the $k$ largest elements seen so far. Consequently, once all elements are processed, the root of the min-heap represents the $k^{th}$ largest element.

The slides below illustrate the core idea of our algorithm: