Find the kth largest number without sorting everything. Quickselect partitions around a pivot, which lands in its final sorted spot, and then keeps only the side that holds index n−k, for O(n) average time and O(1) space.
▼The problem
LeetCode 215 (Medium). Given an integer array nums and an integer k, return the k-th largest element: the k-th in sorted order, not the k-th distinct.
Examples (LeetCode's): [3,2,1,5,6,4], k = 2 → 5 (the walkthrough example); [3,2,3,1,2,4,5,5,6], k = 4 → 4 (both 5s count: 6, 5, 5, 4).
The solution
def findKthLargest(nums, k):
target = len(nums) - k
lo, hi = 0, len(nums) - 1
while True:
pivot, store = nums[hi], lo
for j in range(lo, hi):
if nums[j] <= pivot:
nums[store], nums[j] = nums[j], nums[store]
store += 1
nums[store], nums[hi] = nums[hi], nums[store]
if store == target: return nums[store]
if store < target: lo = store + 1
else: hi = store - 1Transcript
Kth Largest Element in an Array. Given numbers and k, return the k-th largest in sorted order; repeats each count.
Take three, two, one, five, six, four, with k two: the second largest is five. With three, two, three, one, two, four, five, five, six and k four, both fives count, so it's four.
Sorting everything and reading index n minus k costs n log n, ordering numbers we never needed.
Quickselect does less. Pick a pivot, the last number, and partition: smaller or equal numbers move to its left, bigger ones to its right. Now the pivot sits exactly where sorting would put it.
If that's index n minus k, we're done. If not, the answer is on one side, so drop the other and repeat.
In code, a store pointer marks where the next small number goes. Each number no bigger than the pivot swaps there, and the pointer moves on. Then the pivot swaps in; return it, or narrow the range.
Back to our example: the target is index four. The pivot is four. Three, two and one are no bigger; five and six are bigger. The pivot swaps into index three, below the target, so keep the right side. The new pivot, five, swaps into index four. That's the target: the answer is five.
On average each round drops half: n, plus n over two, plus n over four, about two n. Linear time, constant space. Always-bad pivots cost n squared; a random pivot makes that unlikely. A size k min-heap also works, in n log k.
Pick a pivot, partition, keep one side. That's Kth Largest Element in an Array.