3
$\begingroup$

I need to find the kth smallest element in an unsorted array of non-negative integer.

kth smallest element is the minimum possible n such that there are at least kth elements <= n.

The rub here is that the array is read only so it can't be modified. Also i have to do it in constant space.

Can anybody help come up with the most optimal solution ?

$\endgroup$
  • $\begingroup$ What's wrong with brute-forcing it in $O(nk)$ time and $O(k)$ space? $\endgroup$ – greybeard Jul 1 '18 at 11:53
  • $\begingroup$ @greybeard you mean $O(nk)$ time and $O(1)$ space? $\endgroup$ – Albert Hendriks Jul 4 '18 at 16:27
  • $\begingroup$ @AlbertHendriks: while I can see that it doesn't matter with a "Real RAM", I'd frown iterating the input more than once, hence $k$ candidates in preference over one (and a count). $\endgroup$ – greybeard Jul 4 '18 at 19:37
  • $\begingroup$ OP mentioned they wanted an algorithm running in constant space. $\endgroup$ – Yuval Filmus Jul 6 '18 at 9:06
4
$\begingroup$

There is a simple randomized algorithm running in expected $O(n\log n)$ time. The algorithm is a variant of the better known algorithm QuickSelect.

The algorithm maintains a pair of values $a \leq b$, initially $-\infty$ and $+\infty$ (or, the minimum and maximum values of the array). At each round, it chooses a uniformly random element $c$ in the range $[a,b]$ from the array, and computes its order statistics, i.e., the value $\ell$ such that $c$ is the $\ell$th smallest element in the array.

  • If $\ell = k$, then we return $c$.
  • If $\ell > k$, we replace $b$ with $c$.
  • If $\ell < k$, we replace $a$ with $c$.

If $a = b$ then we return $a$. Otherwise, we continue for one more iteration.

Each iteration takes time $O(n)$, so in order to estimate the running time of the algorithm, we need to estimate the number of rounds. We will keep track of the number of "live" elements, initially $n$. The algorithm ends when the number of live elements gets down to 1 (or even sooner, if there are repeated elements).

Let us denote by $n_t$ the number of elements after $t$ rounds, so that $n_0 = n$. The exact distribution of $n_{t+1}$ given $n_t$ depends on the location of the $k$th order statistics among the live elements. Let us suppose that the $k$th order statistics is the $\ell$th live element. Without loss of generality, $\ell \leq (n_t+1)/2$. Suppose that we choose the $r$th order statistic, so $r$ is uniform over $1,\ldots,n_t$. Then:

  • If $r = 1,\ldots,\ell-1$ then $n_{t+1} = n_t - (r-1)$.
  • If $r = \ell$ then $n_{t+1} = 0$.
  • If $r = \ell+1,\ldots,n_t$ then $n_{t+1} = r$.

In total, the expected value of $n_{t+1}$ is $$ \frac{1}{n_t} [(n_t + \cdots + n_t-\ell+2) + (\ell+1 + \cdots + n_t)]. $$ The number of summands is constant, and the worst case is when $\ell = (n_t+1)/2$, in which case the expected value of $n_{t+1}$ is $$ \frac{(\frac{n_t+1}{2}+n_t)\frac{n_t-1}{2}}{n_t} \leq \frac{3}{4}n_t. $$ Induction shows that $\mathbb{E}[n_t] \leq (3/4)^t n$, and so the expectation drops below 1 for $t = O(\log n)$.

While this doesn't quite show that the expected number of iterations is $O(\log n)$, more refined arguments do, and they moreover show that the number of iterations is $O(\log n)$ with high probability.


Here are some hints on how to implement the algorithm. The crucial step is to choose a uniformly random element $c$ in the range $[a,b]$ from the array. There are at least two ways to go about it, both taking $O(n)$:

Reservoir sampling

  1. Initialize $N = 0$ and $X = \bot$.

  2. Go over all elements of the array. For each element $x$, if $a \leq x \leq b$:

    • Increment $N$.
    • Replace $X$ with $x$ with probability $1/N$.
  3. Return $X$.

Linear scan

  1. Count the number of elements in the array between $a$ and $b$ — say the answer is $N$.

  2. Draw a random integer $i$ between 1 and $N$.

  3. Go over the array again, and return the $i$th element between $a$ and $b$.

$\endgroup$
  • $\begingroup$ The analysis, as written, actually only works in the case of distinct elements. But the algorithm should work with similar efficiency in the general case as well. $\endgroup$ – Yuval Filmus Jun 30 '18 at 21:31
  • $\begingroup$ How do you pick an element $c$ "uniformly random in the range $[a,b]$ from the array" in $O(n)$? Does that mean that each element of the array is equally likely to be picked, or the value is equally distributed in $[a,b]$? $\endgroup$ – Mario Carneiro Jun 30 '18 at 23:28
  • $\begingroup$ @MarioCarneiro stackoverflow.com/questions/9401375/… $\endgroup$ – Bulat Jun 30 '18 at 23:31
  • 1
    $\begingroup$ I mention this because it's a nontrivial part of the full algorithm. It should be made more obvious in the answer if reservoir sampling is being used. $\endgroup$ – Mario Carneiro Jul 1 '18 at 1:59
  • $\begingroup$ You don't have to do we reservoir sampling, though it's certainly a possibility. Instead, you can count the eligible elements, draw an index, and then go over the array again to figure d the chosen element. $\endgroup$ – Yuval Filmus Jul 1 '18 at 5:33
1
$\begingroup$

Maybe you're looking for an obvious answer that satisfies the requirements.

You can loop through the array and find the smallest element ($x$) and how many times it occurs ($y$).

In the next loop you find the next smallest element ($x'_{>x}$) and add how many times it occurs to the count $y$.

Continue until $y$ reaches $k$. It takes $O(nk)$ time and constant space.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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