2
$\begingroup$

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.

$\endgroup$
13
  • $\begingroup$ Hint: if $x$ is the median of medians of these arrays, then at least 1/4 of elements are less than $x$, and at least 1/4 of elements are greater than $x$. This allows you to use "kind of" a binary search. $\endgroup$
    – Dmitry
    Dec 16, 2022 at 17:08
  • $\begingroup$ What kind of binary search, could yo give a hint about that? $\endgroup$
    – ErroR
    Dec 16, 2022 at 18:01
  • $\begingroup$ @Dmitry Your hint is nice. However, assuming $k$ is smaller than half of the total number of elements, not a single element can be removed without further information, let alone 1/4 of all elements. You may want to check my answer. $\endgroup$
    – John L.
    Dec 23, 2022 at 22:08
  • $\begingroup$ @JohnL., Not sure what you mean by that. Given the median of the medians, you can determine whether its rank is greater or less than $k$ (by determining its rank in every array). If it's greater than $k$, you delete all the elements which are greater than it (similarly if it's less than $k$). At the first iteration, you will remove at least $\frac 14$ of the elements. The only problem is that the sizes of the arrays are no longer equal, which (I didn't check this part much) can be addressed by ignoring very small arrays when selecting the median of medians. $\endgroup$
    – Dmitry
    Dec 23, 2022 at 23:45
  • $\begingroup$ @Dmitry Please check my updated answer, which give a counterexample to your approach. $\endgroup$
    – John L.
    Dec 24, 2022 at 0:20

1 Answer 1

3
$\begingroup$

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)$.
$\endgroup$
4
  • $\begingroup$ Thank you, but I have an idea as follow: first we find median of medians of $m$ sorted arrays, let it be $M$, then we compare $k$ with $M$ and recurs. Can this idea leads to answer? $\endgroup$
    – ErroR
    Dec 23, 2022 at 16:26
  • $\begingroup$ The idea to use the median of medians of $m$ sorted arrays to eliminate some elements is the first step in my journey to find/design/create a working solution. It is a great idea, but it does not work, since no reduction of the problem can be done! Not a single element can be removed without further information even if we assume $k<T/2$. Then I started to find a way/a situation that allows at least one element to be removed. And more elements at one round. Etc. $\endgroup$
    – John L.
    Dec 23, 2022 at 22:03
  • $\begingroup$ Can you check this problem? cs.stackexchange.com/questions/157456/… $\endgroup$
    – ErroR
    Feb 10, 2023 at 11:24
  • $\begingroup$ It's possible describe a in briefly and simple manner your idea for find $k-th$ element? Thank you. $\endgroup$
    – ErroR
    Feb 10, 2023 at 13:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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