0
$\begingroup$

kth smallest in one sorted array, just take O(1) time

kth smallest in two sorted arrays, there is a binary search algorithm, take O(log k) time

kth smaleest in n sorted arrays, we can use min-heap, takes O(k log n). However, when n = 1 or 2, it's essential brute-force linear scan which takes O(k).

Is there more optimized algorithm for kth smallest in n sorted arrays which will keep optimized when n = 2?

$\endgroup$
0

1 Answer 1

0
$\begingroup$

I think something like this could work:

Given $n$ arrays $A_1, …, A_n$ and an integer $k$, finding the $k$-th smallest element of those arrays can be done by finding $n$ "cuts" in those arrays such that the total number of elements before cuts is equal to $k$. The $k$-th smallest element is then one of the elements just before cuts in one of the arrays.

In details, if the arrays are of lengths $N_1, …, N_n$, we need to find indices $i_1, …, i_n$ such that for all $1\leqslant j \leqslant n$, we have $0\leqslant i_j\leqslant N_j$, and $\sum\limits_{j=1}^ni_j = k$.

To ensure the cuts are well done, for $j\neq j'$, we also need $A_j[i_{j}-1] \leqslant A_{j'}[i_{j'}]$.

The $k$-th smallest element is then $\max\limits_{j=1}^nA_j[i_{j}-1]$ (note that some of those may not exist if $i_j=0$).

The idea of the algorithm is some kind of double divide and conquer. Details may be missing, but I think this works:

  • if $n = 1$, find the cut in $\mathcal{O}(1)$ time;
  • otherwise:
    • let $k_1 = 0$ and $k_2 = k$;
    • while $k_2 > k_1 + 1$:
      • let $\ell = (k_1 + k_2) / 2$
      • find the cuts for the $\ell$-th smallest element $x$ in arrays $A_1, …, A_{\frac{n}2}$;
      • find the cuts for the $(k-\ell)$-th smallest element $y$ in arrays $A_{\frac{n}2+1},…,A_n$;
      • if the cuts are well done, return $\max(x, y)$;
      • otherwise, if $x < y$, $k_1$ becomes $\ell$;
      • otherwise, $k_2$ becomes $\ell$

To check if cuts are well done, you need to check if $x \leqslant A_{j'}[i_{j'}]$ for $j'\in \{\frac{n}2+1, …, n\}$ and if $y\leqslant A_{j'}[i_{j'}]$ for $j'\in \{1, …, \frac{n}2\}$.

For the complexity, let $C(n)$ be the time complexity for the search of the $k$-th smallest element in $n$ sorted arrays. Given the previous algorithm, we get: $$C(n) = \log_2 k (2C\left(\frac{n}2\right) + \mathcal{O}(n))$$

Using the master theorem, we get $C(n) = \mathcal{O}(n(\log_2 k)^{\log_2 n})$.

We get $C(1) =\mathcal{O}(1)$ and $C(2) = \mathcal{O}(\log_2 k)$.

$\endgroup$

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.