Best way to retrieve K largest elements from large unsorted arrays?

Another way of solving this is using Quickselect. This should give you a total average time complexity of O(n). Consider this:

1. Find the *k*th largest number *x* using Quickselect (*O(n)*)
2. Iterate through the array again (or just through the right-side partition) (*O(n)*) and save all elements *≥ x*
3. Return your saved elements

(If there are repeated elements, you can avoid them by keeping count of how many duplicates of x you need to add to the result.)

The difference between your problem and the one in the SO question you linked to is that you have only one million elements, so they can definitely be kept in memory to allow normal use of Quickselect.

Related Articles

js interview questions