Well known problem. - Codeforces

mkagenius's blog

By mkagenius, 12 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.

kth, union, array

-7

mkagenius
12 years ago
2

Comments (2)

Write comment?

rlac

12 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.

→ Reply