I'm not sure why this solution holds:


For example, $A=[1, 1, 2, 3, 10, 15]$ and $B=[-1, 2, 3, 4, 6, 7]$ then *k=8*th smallest element would be 4 as it appears in 8th position of the merged sorted array=$[-1, 1, 1, 2, 2, 3, 3, 4, 6, 7, 10, 15]$.

A trivial solution would be to do a merge operation as we do in merge phase of the merge sort while increasing a counter whenever we chose an element in the merge phase (i.e. when we increase one of the marker index). This guarantees $O(k)$ time solution. Can we do better?

As both the arrays are sorted so in best case scenario when both arrays are identical then kth element in the merged array would be k/2 the element in one of the arrays. If they are not identical then kth element will reside in one of the 2 partitions of one of the sorted arrays. This signals us that we could discard searching in some partitions. How? Of course we can try binary search over two sorted arrays.

We can try to find two mid point index i and j in the two arrays respectively such that A[i] falls in between B[j-1] and B[j] i.e. $B[j-1] < A[i] < B[j]$. Notice that this guarantees that A[i] is that (i+j+1) th smallest element because there is exactly j elements in B less than A[i] (because $A[i] > B[j-1]$) and there are exactly i elements in A less than $A[i]$. So, if we want to find kth smallest element then we need to find middle element $A[i]$ and $B[j]$ maintaining the invariant that $i+j+1 = k$.

$i + j = k – 1$

Also note that if we have $A[i] > B[j]$ then we know that kth smallest can't be in $A[i+1..]$ or in $B[..j]$. So we can discard these two halves. This guarantees logarithm search time. Also, note that if $A[i] > B[j]$ then we are already discarding elements in $B[..j]$ which are smaller than kth smallest. So, we arrive the following conclusions -

$A[i] > B[j]$ left partition of B are smaller and right partition of A are greater than kth smallest.
Discard $A[i+1..r1]$ and $B[p2..j]$
Update $k = k-(j-p2+1)$ as we are discarding smaller elements in $B[p2..j]$
Otherwise left partition of A are smaller
   and right partition of B are greater than kth smallest.
Discard $A[p1..i]$ and $B[j+1..r2]$
Update $k = k-(i-p1+1)$ as we are discarding smaller elements in $A[p1..i]$

I understand 99% of this. To find the $k$th smallest element, just try to find an $A[i]$ such that $B[j-1]<A[i]<B[j]$ such that $i+j=k-1$.

So from here on out, let $i+j=k-1$ be the constraint.

What I DON'T understand is why, if $A[i]>B[j]$, then we keep $A[i]$ as a possible candidate for the $k$th largest element. In the algorithm from the link, he says to keep $A[0,...,i]$ and $B[j+1,...]$.

I don't know why we don't keep $A[0,...,(i-1)]$ instead of $A[0,...,i]$. If $A[i]>B[j]$, then $A[i]$ is greater than or equal to $j+1$ elements in $B$ along with $i$ from $A$, thus it won't be the $k$th smallest element since $(i+j+2)>k$.

And I tried to implement this algorithm, my implementation only works when I keep $A[0,...,i]$ and not $A[0,...,(i-1)]$. I simply don't understand why we keep $A[i]$ when it clearly cannot be the $k$th smallest element when $A[i]>B[j]$.

Any thoughts? I don't see where I'm wrong here.

  • $\begingroup$ It seems like I was right and the link’s solution explanation is incorrect because $k$ should instead denote that there are $k$ elements less than a value, not the $k$th smallest element. So $k=0,1,...,n-1$ where $n$ is the total number of elements in the union of the two arrays. $\endgroup$ – Glassjawed Apr 9 '19 at 21:44
  • $\begingroup$ Have you run the code in that article? If you have not, you should go ahead to run them now. If yes, please edit the question to show what you have tested and what are the result. $\endgroup$ – John L. Apr 10 '19 at 1:11
  • $\begingroup$ Yes I did. The code works (implemented in Python). It was that the explanation provided on the website didn't lineup exactly with the code. $\endgroup$ – Glassjawed Apr 10 '19 at 2:44

Your Answer

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

Browse other questions tagged or ask your own question.