I am trying to design an efficient algorithm that retrieves the ith to jth largest elements in an array. For example, if the following array is the input:

[10, 14, 18, 3, 21, 25, 27]
i = 2
j = 4

The following array is returned:

[25, 21, 18]

18 is the 4th largest element in the array and 25 is the 2nd smallest element in an array. I've done a problem where you retrieve a list of the K largest elements in an array: in such a problem, the solution is pretty trivial (using a fixed-size minimum heap of size K to keep track of the K largest elements). In this case however, a heap seems out of reach to use because the minimum heap can only remove the smallest element from the heap (removing the kth smallest element within the heap seems really inefficient).

I could do QuickSelect (j - i) times to get all the elements, but that means doing a linear O(n) walkthrough (j - i) times, which yields a total time complexity of O((j-i) * n), but I was thinking about if it's possible to quicken the algorithm's time complexity to just O(n). Is there an O(n) algorithm to solve this problem?

  • $\begingroup$ If $i=1$ and $j=n$, are you essentially sorting this array? $\endgroup$
    – xskxzr
    Sep 17 '19 at 6:28
  • $\begingroup$ @xskxzr Yes, I am essentially sorting this array if i = 1 and j = n. $\endgroup$
    – Henry Zhu
    Sep 17 '19 at 6:33

I could do QuickSelect (j - i) times to get all the elements

Overkill. Two calls to QuickSelect and one linear pass are sufficient.


If you don’t know quickselect: Just implement Quicksort, but every time Quicksort would sort a sub array, you don’t do it if you don’t need it to find out which items I to j are.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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