World's most popular travel blog for travel bloggers.

# \$k\$th Largest Algorithm in a range \$[k, k+c]\$

, ,
Problem Detail:

The well-known algorithm for computing the \$k\$-th largest element in an unsorted array of size \$n\$ runs in \$O(n)\$ time.

How about for a range \$[k, k+c]\$, where \$c\$ is not necessarily independent of \$n, k\$? The obvious "brute-force" algorithm is to find the \$k\$th largest using the original \$O(n)\$-time algorithm, then the \$k+1\$-th largest the same way, ..., find the \$k+c\$-th largest (and also, the algorithm outputs these in sorted order). However, this takes \$O(nc)\$ time, and \$c\$ can possibly be \$\Theta(n)\$, which can lead to an \$O(n^2)\$ algorithm. In this case, we could have just sorted the array and extracted the elements, which takes \$O(n \log n)\$ time.

Is there a better (known) way of doing this? I can't find any references online.

Step 1. Use QuickSelect to find the \$k\$th largest number in the array. Call it \$x\$.

Step 2. Use QuickSelect to find the \$k+c\$th largest number in the array. Call it \$y\$.

Step 3. Find all elements in the array that are at least \$x\$ and at most \$y\$. This can be done by simply iterating over the array and comparing each element to \$x\$ and \$y\$.

Each step can be done in \$O(n)\$ time. Therefore, the total running time is \$O(n)+O(n)+O(n) = O(n)\$ time.