mkagenius's blog

By mkagenius, 9 years ago, In English
Q. Find the kth element from the union of two sorted arrays.(one of size n, other of size m).
===================================
Although there are numerous resources on the web that claim to solve it in log(n) or log(k) . But I have not found a complete solution which takes care of all cases, such as  k  < n or k < m or k > 2*n etc.,
i mean none took care of all cases.

So, I tried to get log(n+m) complexity, but i could not achieve it taking all kind of cases into considerations, every time i miss some of the case.
===================================
A help is needed here to get a full solution.
 
 
 
 
  • Vote: I like it
  • -7
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +13 Vote: I do not like it
Look this problem.
Given an integer n and two sorted arrays A and B of length n, find the nth element in the union of the two arrays.
This problem can be solved easily using binary search.

Let:
A = {a1, a2, ..., a(n/2), a(n/2+1), ... a(n-1), an}
B = {b1, b2, ..., b(n/2), b(n/2+1), ... b(n-1), bn}
C = A union B.

bool cmp1 (int iA, int iB)
{
    return A[iA] <= B[iB];
}

if cmp1(n/2, n/2) then we have that a(n/2) <= b(n/2).
Now, observe that any number in A[1...n/2] will be fixed in the first (n - 1) numbers of C, because there are n + 1 numbers that are greater or equal to they. These numbers are:
a(n/2+1), ... a(n), b(n/2), ..., b(n).
In other hand, not number in B[n/2+1, ..., n] will necessarily be in the first n numbers of C, because there are n  numbers that are smaller or equal to they. These numbers are:
a1, ..., a(n/2), b1, ..., b(n/2).
Now, the nth number in C will be the (n/2)th number in (A[n/2+1...n] union B[1...n/2]).

The case when !cmp1(n/2, n/2) is analogous.

Now let see how transform your problem to this one.
Let A and B your input arrays (size(A) = n and size(B) = m)
if n < k we can fill A with values equal to infinity and now n = k.    (filling process)
if m < k we can fill B with values equal to infinity and now m = k.

Let C = (A union B).
Not number in A[k+1...n] will be the kth number in C because there are k numbers that are smaller or equal to they.
These numbers are A[1...k].
Not number in B[k+1...n] will be the kth number in C because there are k numbers that are smaller or equal to they.
These numbers are B[1...k].

Now your problem is reduced to find the kth element in two arrays of size k (A[1...k], B[1...k]), that is exactly the above problem. The complexity is O(logk)

NOTE: The filling process is abstract. We can simulate it replacing cmp1 by cmp2:

bool cmp2 (int iA, int iB)
{
    if (iB >= m)
        return true;

    if (iA >= n)
        return false;
        
    return A[iA] <= B[iB];
}

There is other solution with complexity O (min (k, m, n)), but it's difficult for me explain it in english.
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Ah, nice!
    Thanks.
    That part about filling it with inf. upto k, was brilliant.
    (how could I miss it. so obvious, thanks again.)