Second Largest with Minimum Comparisons

Reported in interviews at D. E. Shaw Hudson River Trading Radix Trading Two Sigma

Problem statement

You have an array of $n$ distinct numbers. Design an algorithm that finds the second largest element using at most $n + \lceil \log_2 n \rceil - 2$ comparisons in the worst case.

  1. Describe the algorithm and prove it achieves this bound.
  1. Prove that no comparison-based algorithm can do better -- i.e., $n + \lceil \log_2 n \rceil - 2$ is a lower bound on the worst-case number of comparisons needed to find the second largest.
Show hint

Which elements are the only possible candidates for the runner-up once you know who beat whom?

Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.

Related free problems