# Algorithm Design: Efficient O(n) algorithm to get the ith to jth largest elements in an array

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?

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