268. What is the minimum number of comparisons needed to find both the minimum and maximum of n elements?
MediumSorting
Technical
Show model answer
Finding each separately costs 2n − 2 comparisons. Process elements in pairs instead: compare the two elements of a pair with each other (1 comparison), then compare the smaller with the current minimum and the larger with the current maximum (2 more). That is 3 comparisons per pair, or ⌈3n/2⌉ − 2 in total (exactly 3n/2 − 2 for even n).
This is optimal: an adversary argument shows any algorithm needs at least ⌈3n/2⌉ − 2 comparisons, because each comparison can do little to rule elements out of being both the min and the max candidate. Time is still O(n); the improvement is in the constant.