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.
===================================
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.
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.
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.
Thanks.
That part about filling it with inf. upto k, was brilliant.
(how could I miss it. so obvious, thanks again.)