Quick Select
Finds the kth smallest/largest element
Average: O(n)
Worst: O(n²)
Algorithm
Given an integer array, find the kth largest element.
The easiest way? Sort the array. But that’s O(n log n).
Can we do better?
Sure! How about using a PriorityQueue? That’s O(n log k)!
Can we do even better?
Use Quick Select; the algorithm’s linear on average.
Why O(n)? The algorithm recurs only for the part that contains the kth largest element. If we assume it recurs half the list each time, it processes n elements in the first recursive call, n/2 in the second, n/4 in the third, and so on, until there’s only 1 element remaining.
Remember geometric series?
1 + (1 / 2) + (1 / 4) + ... + (1 / n) = 2. Similarly,
n + (n / 2) + (n / 4) + ... + 1 = 2n.
Average: O(n)
Worst: O(n²) if the array is already sorted
LeetCode
215. Kth Largest Element in an Array
Python | Java
