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 .

  • 4
    How about using a min-heap? – Shir Jun 23 '13 at 14:44
  • 1
    Look at k-skyband and top-k computation. The paper cs.sfu.ca/~jpei/publications/subsky_tkde07.pdf has a nice review of related literature. – András Salamon Jun 23 '13 at 14:44
  • 1
    Shir-I have examined the min-heap idea . however , in order to print the k smallest numbers in min heap is in O(klogn) time and not O(k) as required – Idan Jun 23 '13 at 14:47
  • 4
    @idannik: Why do you think it takes $\Omega(k \log n)$ time to find the $k$ smallest elements in a min-heap? – Kristoffer Arnsfelt Hansen Jun 23 '13 at 20:07
  • 8
    I don't think this is research-level. It looks like an assignment. Where did you find it? – Kaveh Jun 23 '13 at 21:20
up vote 16 down vote accepted

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.
  • 1
    I guess the outer loop is supposed to be 'for i in $\{2^{\lceil\lg n\rceil},\dots,4,2,1\}$'. Is your algorithm different from the one in Yuval Filmus' answer? – Radu GRIGore Jun 23 '13 at 20:14
  • 2
    This is a generalization of my algorithm to arbitrary $n$. It also spells out some implementation details which were (deliberately) left out from my answer. – Yuval Filmus Jun 23 '13 at 20:39
  • 2
    @YuvalFilmus Do you wish to imply by your comment that my answer is unethically close to yours? This is the solution which came to mind when I reviewed the question. I saw that you posted a similar one, but found it unclear, so I wrote my own (as opposed to doing a major edit of yours). What matters ultimately is the quality of the answers on the systems, not really who wrote them: the badges and reputation are only incentives, not objectives in themselves. – Jeremy Jun 24 '13 at 12:28
  • 4
    @Jeremy Not at all; Just that the two solutions are the same (but yours works for arbitrary $n$), and that I didn't flesh out the details in case it was actually a homework question. – Yuval Filmus Jun 24 '13 at 14:40
  • 2
    Oh :( Sorry about that then. (Althought I would still think giving complete answers to be a priority over assignment suspicions) – Jeremy Jun 25 '13 at 13:31

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.

  • 1
    Naturally. If the array is sorted that you can solve this in $O(1)$ without preprocessing. Perhaps you are not aware of the linear time selection algorithm that can find the $k$th largest element in time $O(n)$? – Yuval Filmus Jun 23 '13 at 16:03
  • 4
    @Yuval Filmus: Are you not running the algorithm $\log n$ times, for a total of $n \log n$ steps? Or did you have some kind of interleaving in mind? – András Salamon Jun 23 '13 at 17:12
  • 3
    @AndrásSalamon: If you read the answer given by Jeremy (which looks to me almost the same as this one) you see that you first process the whole array, then the first half, and so on. – Radu GRIGore Jun 23 '13 at 20:20
  • 3
    @AndrásSalamon Radu is correct. After you find the median, you partition the array (in-place) into its lower and upper half, then recurse on the lower half. The running time is then proportional to $n+n/2+n/4+\cdots+1 < 2n$. – Yuval Filmus Jun 23 '13 at 20:31
  • 5
    Incidentally this algorithm appears as a subroutine in my answer to an earlier question: cstheory.stackexchange.com/questions/17378/… – David Eppstein Jun 23 '13 at 23:12

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.

  • 1
    The original question mentions that $k$ is not known at preprocessing time.... – Jeremy Jun 23 '13 at 19:35
  • 1
    I see. My mistake. – jbapple Jun 23 '13 at 22:17

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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