Returning $k^{th}$ smallest number in $m$ sorted arrays

Question

Given $m$ sorted arrays $A_1,A_2,\dots,A_m$, also $\mid A_i\mid=n$ for each $i=1,2,\dots,m$. How we can compute $k^{th}$ smallest number in union of $A_i$s (i.e. $\cup_{i=1}^nA_i$) in at most $O(m\log mn)$?

$I.$ If I use Minheap to find $k^{th}$ element, th running time will be $O(m+k\log mn)$, so that $k$ can be $O(nm)$ so this idea is not the case.

$II.$ I try to use divide and conquer approach as follow:

a. Divide $m$ sorted arrays into two equal halves.

b. find $k^{th}$ in first half and second half.

at this stage I get stuck and have no idea, however, I prefer to find out some hints not complete solution.

Answer 1

Can we just use the median of medians of these arrays?

One strategy is to find the median of medians of these arrays, name it $x$. At least $T/4$ elements are less than $x$, and at least $T/4$ elements are greater than $x$, where $T$ is the number of all elements. If $k<T/2$, we can delete those $T/4$ elements that are greater than $x$; if $k\ge T/2$, we can delete those $T/4$ elements that are less than $x$. Then recur.

However, this strategy does not work by itself. It turns out that not a single element can be removed without further information.

Here is an example. Consider the sorted row arrays below, where we have $49$ numbers. Suppose we are asked to find $23$-th smallest element. $$\begin{matrix} &a_1:= &(1,&1,&1,&2, &13,&13,&13)\\ &a_2:= &(1,&1,&1,&3, &13,&11,&13)\\ &a_3:= &(1,&1,&1,&4, &13,&11,&13)\\ &a_4:= &(1,&1,&1,&5, &13, &13,&13)\\ &a_5:= &(1,&1,&1,&6, &7, &8, &9)\\ &a_6:= &(10,&10,&10,&11, &13,&13,&13)\\ &a_7:= &(10,&10,&10,&12,&13,&13,&13) \end{matrix}$$

Since $23<49/2$, we will remove each element that is greater than the median in its respective array if that median is greater than the median of median of all arrays.

The median of the medians $2,3,4,5,6,11,12$ is $5$. Since array $a_5$ is an array with median $6$ that is greater than $5$, we will remove $7, 8, 9$ in it. However, $9$ is the $23$-th smallest elements of all elements, the wanted element.

---

However, all are not lost. Dmitry provides the following remedy. "Given the median of the medians, you can determine whether its rank is greater or less than $k$ (by determining its rank in every sorted array using binary search). If it's greater than $k$, you delete all the elements which are greater than it (similarly if it's less than $k$)." With some further tweaking , we could arrive at an algorithm that runs in $O(m\log n\log (mn))$ time.

The ideas

For simplicity, I will be ignoring off-by-one errors and treating some fractions as if they were integers from time to time. A rigorous and working implementation will be provided later.

Imagine the algorithm will run some logic repeatedly, removing elements that are not possible to be the $k$-th smallest number in each round. After each round, $k$ will be updated accordingly.

One round of removal

We want to remove as many element as possible in each round. However, it is either impossible or too slow to remove at least one element from each array or remove a constant number of elements from each array. Instead, we should accomplish in each round,

• select a significant portion of arrays
• remove a significant portion of elements at front or at back from each selected array (what remain of each array is a subarray of the original array).

Assume $k>T/2$, where $T$ is the number of remaining elements. The plan for the other case, when $k\le T/2$ is symmetric.

Each array $\overline A_i$ can be viewed as $\frac23|\overline {A_i}|$ elements above $pivot_i$ and $\frac13|\overline {A_i}|$ elements below $pivot_i$, where $\overline {A_i}$ is the subarray of $A_i$ that consists of the remaining elements in $A_i$ while $pivot_i$ is the $\frac13|\overline {A_i}|$-th smallest element in $\overline {A_i}$. Elements that are equal to $\overline {A_i}$ are not mentioned since they will be treated as if they were above or below $pivot_i$ appropriately.

We then collect the pair $(pivot_i, |\overline {A_i}|$) for all arrays.

We can adapt a linear selection algorithm to select the "$T/5$-th" smallest pivot, named it $J$, treating each pair $(pivot_i, |\overline {A_i}|$) as representing $|\overline {A_i}|$ elements of value $pivot_i$, where $T=\sum_i|\overline {A_i}|$, the total number of remaining elements. Since there are at most $m$ pairs of $(pivot_i, |{\overline {A_i}}|)$, we can select $J$ in $O(m)$ time.

For each $pivot_i\le J$, remove all elements in $\overline{A_i}$ that are below $pivot_i$. Since $\frac45T\cdot\frac23=\frac8{15}T>\frac T2$ elements that are above $J$ remain and all removed elements are smaller than $J$, the $k$-th element must have not been removed! Note the removal of elements in one array takes $O(1)$ time; all we do is to increase the index in $A_i$ of the first element of $\overline {A_i}$ by $\frac{|\overline {A_i}|}3$.

One round of removal can be done in $O(m) + O(m) + m O(1)=O(m)$ time. It removes $\frac T5\cdot\frac13=\frac T{15}$ elements.

$O(\log mn)$ rounds of removal

The number of all elements is $mn$ initially.

Since $\frac1{15}$ of all remaining elements are removed in each round, after $O(\log mn)$ rounds, the number of remaining element would be reduced to $O(1)$, ideally. However near the end of this process when there are less than $15$ remaining elements in an array, the off-by-one errors and mistreated fractions might not be ignored. In the end, we end up with less than $15m=O(m)$ elements. ($15$ might be reduced; however, we need just a constant.)

Then we will use a linear selection algorithm to find the $k$-th element.

The total running time is $O(m)O(\log mn) + O(m)=O(m\log mn)$.