How to Find the Kth Largest Element in an Array

Given an unsorted array, find the element that would be at the Kth position if the array were sorted in descending order. The first largest is the maximum, the second largest is the second biggest value, and so on. Multiple approaches exist with very different time complexities.

The simplest approach is to sort the array in descending order and return the element at index K minus one. This is easy to implement and always correct but takes O(N log N) time. It is acceptable for small inputs but not optimal for large ones.

Create a Min-Heap and insert the first K elements. Then iterate through the remaining elements. For each element, if it is greater than the top of the Min-Heap, remove the top and insert the current element. After processing all elements, the top of the Min-Heap is the Kth largest element.

The Min-Heap of size K always holds the K largest elements seen so far. The smallest of those K elements sits at the top. Whenever you find a larger element, it belongs in the top K and displaces the current smallest. After all elements are processed, the top is exactly the Kth largest.

QuickSelect is a variation of Quick Sort that only recurses into one side of the partition. After partitioning, if the pivot lands at index K minus one from the end, it is the answer. If the pivot is too far right, recurse left. If too far left, recurse right. Average time complexity is linear.

Choose a pivot, usually the last element. Partition the array so elements greater than the pivot come first and elements smaller come after, since you are looking for the Kth largest. After partitioning, the pivot is in its final position. Compare this position with K and decide which side to recurse into.

Use sorting when the input is small and simplicity matters. Use the Min-Heap approach when K is small or when elements arrive as a stream and you cannot store them all at once. Use QuickSelect when you need the best average-case performance on a static array and are comfortable with the implementation.