# Find the kth smallest element in an unsorted array of non-negative integers

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 ?

• What's wrong with brute-forcing it in $O(nk)$ time and $O(k)$ space? – greybeard Jul 1 '18 at 11:53
• @greybeard you mean $O(nk)$ time and $O(1)$ space? – Albert Hendriks Jul 4 '18 at 16:27
• @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). – greybeard Jul 4 '18 at 19:37
• OP mentioned they wanted an algorithm running in constant space. – Yuval Filmus Jul 6 '18 at 9:06

## 2 Answers

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$.

• 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. – Yuval Filmus Jun 30 '18 at 21:31
• 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]$? – Mario Carneiro Jun 30 '18 at 23:28
• @MarioCarneiro stackoverflow.com/questions/9401375/… – Bulat Jun 30 '18 at 23:31
• 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. – Mario Carneiro Jul 1 '18 at 1:59
• 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. – Yuval Filmus Jul 1 '18 at 5:33

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.