171. Kth Largest Element in an Array

Given an array of n integers and a value k, find the kth largest element (k=1 means the largest).

Input: The first line contains an integer n. The second line contains n space-separated integers. The third line contains the integer k. Output: Print a single integer - the kth largest element.

1 <= k <= n <= 10^5

Using a MIN-heap (not a max-heap) capped at size k is the key, slightly counterintuitive trick - the smallest element of the k largest is exactly what you want easy access to, which is precisely what a min-heap's top gives you.

Find the kth largest value in an array, where k=1 means the single largest. Brute force: Sort the whole array in descending order and index directly into position k-1 - this costs O(n log n), more work than necessary when only the kth value (not a full ordering) is actually needed. Optimised: A min-heap capped at size k only ever needs to track the k LARGEST elements seen so far - since anything smaller than the heap's current minimum can never be among the top k, it's safely discarded immediately, keeping the heap small and each operation cheap.

Sort the entire array in descending order and simply read off the element at index k-1. This works because after a full sort, the k largest values occupy the first k positions in decreasing order, so index k-1 is exactly the kth largest. It is correct but wasteful, since it fully orders every element even though only one position's value is actually needed. Time: O(n log n) Space: O(log n)

Scan the array once while maintaining a min-heap that is only ever allowed to hold k elements: push each new element, and whenever the heap grows past size k, pop the smallest. After the scan finishes, the heap always contains exactly the k largest elements seen, so its root (the smallest among them) is the kth largest overall. This avoids sorting the whole array and instead pays only a small O(log k) cost per element. Time: O(n log k) Space: O(k)

Use Quickselect, the selection variant of quicksort's partitioning step: pick a pivot, partition the array around it, and recurse only into the one side that must contain the kth largest element, discarding the other side entirely instead of sorting it. Because roughly half the remaining elements are eliminated on average each round, this reaches the answer in expected linear time; choosing a random pivot (or median-of-medians) avoids the rare worst case. Time: O(n) average, O(n^2) worst case Space: O(1)

1. Maintain a min-heap capped at size k. 2. For every element, push it into the heap; if the heap grows past size k, pop the smallest (discarding it). 3. After processing the whole array, the heap's top (its smallest remaining element) is exactly the kth largest.

Time: O(n log k) - each of the n elements triggers at most one push and one pop on a heap of size at most k. Space: O(k), for the heap.

k = 1 (the maximum element), k = n (the minimum element), and n = 10^5 with duplicate values.

Be ready to mention the QuickSelect alternative (average O(n), based on quickselect's partitioning) as a faster expected-time approach if asked to push beyond the heap-based solution - a valuable follow-up to have ready.