### mkagenius's blog

By mkagenius, 9 years ago,
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.

• -7

 » 9 years ago, # |   +13 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, # ^ |   0 Ah, nice!Thanks.That part about filling it with inf. upto k, was brilliant.(how could I miss it. so obvious, thanks again.)