Sorting
Order statistics
Why it matters
Dashboards and ranking systems often need one percentile or cutoff, not a complete ordering of every record. Fully sorting millions of values computes positions the caller never reads. For [3, 2, 1, 5, 6, 4], return the second-largest value, 5, without paying to sort all six positions.
Example
Kth Largest Element in an Array
Return the kth largest element in nums (1-based from the top). Duplicates count.
- Input
- nums = [3, 2, 1, 5, 6, 4], k = 2
- Output
- 5
Approach 2 · Resolve the bottleneck
The idea
Keep one example in view
Kth Largest Element in an Array
nums = [3, 2, 1, 5, 6, 4], k = 2→5
The baseline, Sort, then index, is O(n log n) · O(n). The better model below keeps this exact input and removes that bottleneck.
The second-largest value in [3, 2, 1, 5, 6, 4] belongs at ascending index 4. Partitioning around 4 puts it at index 3, proving the target lies right. Discard that irrelevant side instead of brute sorting every value.
The second-largest value in [3, 2, 1, 5, 6, 4] belongs at ascending index 4. If the first random pivot is 4, partitioning places 1, 2, and 3 before it and 5 and 6 after it, so 4 lands at index 3.
Target index 4 is to the right, so ignore indexes 0 through 3. A pivot of 6 lands at 5 and sends the search left; then 5 lands at 4 and is the answer. Random pivots shrink the kept range by a constant fraction on average, so all partition work sums to O(n).
Visual anchor
Kth Largest Element in an Array
nums
Pro
The rest of this is on Pro
The idea above is free. The walkthrough, the cost, and the practice are on Pro.