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

Question

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?

---

Answer 1

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

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

Answer 2

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.