Kth Largest Element in an Array - Video Solutions

Problem Overview: Given an unsorted integer array, return the kth largest element. The array is not sorted and duplicates may exist. The goal is to identify the element that would appear at position k if the array were sorted in descending order.

Approach 1: Min-Heap (Priority Queue) (Time: O(n log k), Space: O(k))

This approach keeps only the k largest elements seen so far using a min-heap. Iterate through the array and push each number into the heap. If the heap size exceeds k, remove the smallest element using pop(). The heap always contains the top k largest elements, and the root represents the kth largest overall. This method works well when k is much smaller than n and leverages efficient heap operations from a heap (priority queue). The approach is easy to implement and predictable in performance.

Approach 2: Quickselect Algorithm (Average Time: O(n), Worst Case: O(n²), Space: O(1) or O(log n) recursion)

Quickselect is a selection algorithm derived from QuickSort. Instead of fully sorting the array, it repeatedly partitions the array around a pivot. After partitioning, the pivot lands in its correct sorted position. Compare this index with the target index n - k. If they match, you found the kth largest element. Otherwise, recurse into the left or right partition depending on where the target lies. This approach uses the partition idea from divide and conquer and avoids unnecessary sorting work. Average performance is linear, making it one of the fastest practical solutions.

Recommended for interviews: Start by mentioning the heap approach since it is straightforward and guarantees O(n log k) time. Then present Quickselect as the optimal solution with average O(n) time. Interviewers typically expect you to recognize that a full sorting pass (O(n log n)) is unnecessary and that selection algorithms can locate the kth element faster.