finding smallest k elements in array in O(k)

Question

This is an interesting question I have found on the web. Given an array containing n numbers (with no information about them), we should pre-process the array in linear time so that we can return the k smallest elements in O(k) time, when we are given a number 1 <= k <= n

I have been discussing this problem with some friends but no one could find a solution; any help would be appreciated!

quick notes: -the order of the k smallest elements is not important -the elements in the array are number , might be integers and might be not (so no radix sort) -the number k is not know in the pre-processing stage.the preprocessing is O(n) time. the function ( find k smallest elements) on O(k) time .

Answer 1

Preprocess the array of $n$ values in time $O(n)$:

• $i\leftarrow n$
• while $i>2$
  • Compute the median $m$ of $A[1..i]$ in time $O(i)$
  • partition $A[1..i]$ into $A[1..i/2-1] \leq m$ and $A[i/2+1..i]\geq m$ in the same time.
  • $i \leftarrow \lfloor i/2 \rfloor$

The total precomputation time is within $O(1+2+4+...+n)\subseteq O(n)$

Answer a query for the $k$ smallest elements in $A$ in time $O(k)$:

• $l\leftarrow \lfloor \log_2 k \rfloor$
• select the $(k-2^l)$th element $x$ of $A[2^l..2^{l+1}]$ in time $O(2^l)\subseteq O(k)$
• partition $A[2^l..2^{l+1}]$ by $x$ in the same time

$A[1..k]$ contains the $k$ smallest elements.

References:

• In 1999, Dor and Zwick gave an algorithm to compute the median of $n$ elements in time within $2.942 n + o(n)$ comparisons, which yields an algorithm to select the $k$th element from $n$ unordered elements in less than $6n$ comparisons.

Answer 2

Assume for simplicity that $n = 2^m$. Use the linear time selection algorithm to find the elements at positions $2^{m-1},2^{m-2},2^{m-3},\ldots,1$; this takes linear time. Given $k$, find $t$ such that $2^{t-1} \leq k \leq 2^t$; note that $2^t \leq 2k$. Filter out all elements of rank at most $2^t$, and now use the linear time selection algorithm to find the element at position $k$ in time $O(2^t) = O(k)$.

Clarification: It might seem that the preprocessing takes time $\Theta(n\log n)$, and that is indeed the case if you're not careful. Here is how to do the preprocessing in linear time:

while n > 0:
  find the (lower) median m of A[0..n-1]
  partition A in-place so that A[n/2-1] = m
  n = n/2

The in-place partitioning is done like in quicksort. The running time is linear in $n + n/2 + n/4 + \cdots + 1 < 2n$, and so linear. In the end, the array $A$ satisfies the following property: for each $k$, $A[0..n/2^k-1]$ consists of the $n/2^k$ smallest elements.

Answer 3

First use $O(n)$ to build a min-heap. It is known that we can use $O(k)$ to find the $k$ smallest elements in a min-heap:

Frederickson, Greg N., An optimal algorithm for selection in a min-heap, Inf. Comput. 104, No. 2, 197-214 (1993). ZBL0818.68065..

Answer 4

Use linear time selection to find the $k$th largest element, then do a partition step from quicksort using the $k$th largest element as the pivot.