Kth Largest Element in an Array
Given an unsorted integer array and an integer k, return the k-th largest element in sorted order (not the k-th distinct element). Aim for better than sorting the whole array.
- 1 ≤ k ≤ n ≤ 10^5
- -10^4 ≤ nums[i] ≤ 10^4
- Only one order statistic is needed, not a full sort
- Partitioning around a pivot tells you which side holds the answer
- Expected linear time is possible
If a problem on n items can be solved from solutions on two halves plus linear-time combination work, the recurrence T(n) = 2T(n/2) + O(n) gives O(n log n). Merge sort's merge step is the template; counting inversions and merging k lists pairwise are direct instances.
Use quickselect: pick a random pivot, partition the array so larger elements come first, and compare the pivot's final position p to k - 1. If they match, return the pivot; if p is larger, recurse into the left part, otherwise into the right part with k adjusted. Only one side is explored, so the expected work is n + n/2 + n/4 + … = O(n).
- A min-heap of size k gives O(n log k) worst case and is the safe choice for streaming input. Sorting is O(n log n). Median-of-medians makes quickselect O(n) worst case but is slow in practice.