Selection and closest pair of points (Fundamental algorithms, Spring 2023, Lecture 3)
Kent Quanrud · 76:16
You can find the kth-smallest element of an unsorted array in linear time—without sorting—by using a carefully chosen “median of medians” pivot, and you can find the closest pair of points in the plane in O(n log n) b...