If we have length $n$ unsorted array such that each element is integer and different, how to find $i$ largest numbers in linear time O(n)? but $i \leq n^{\frac{1}{2}}$.

For example, if we have $A = [11, 6, 8, 1, 9, 100, 88]$ and input $i = 2$, then output is $[100, 88]$ (sorted).


1 Answer 1


Use a selection algorithm to find the $i$th largest number. This can be done in linear time. Then, do a second scan over the array to find all numbers larger than the $i$th largest number. (With many selection algorithms, this last step is unnecessary, as they partition the array into elements smaller than the $i$th largest and larger than the $i$th largest.)

  • $\begingroup$ How can I apply this algorithm to this finding multiple largest numbers problem? $\endgroup$
    – t24akeru
    Mar 27, 2021 at 2:37
  • $\begingroup$ @t24akeru, see edited answer. You should be able to work out the details from here. $\endgroup$
    – D.W.
    Mar 27, 2021 at 5:58
  • $\begingroup$ @D.M. Thank you! One question, is the scanning operation not counted time complexity? $\endgroup$
    – t24akeru
    Mar 27, 2021 at 6:24
  • 1
    $\begingroup$ I would like to add that the classical selection algorithms (quickselect / median of medians) both partition the array so that the largest $i$ elements are also the last elements if you select on the $i$th element. $\endgroup$
    – orlp
    Mar 27, 2021 at 6:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.