Walk through the top k elements pattern and learn efficient selection using heaps.

Central CIP Path

Top K Elements

# 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:


Let's solve the Kth Largest Element in an Array problem using the Top K Elements pattern.

Solution: Kth Largest Element in an Array

Statement▼

Solution

Solution: Kth Largest Element in an Array

Statement▼

Solution