CareerCup

use a derivative of the solution that is used to find the median of the two sorted arrays in log(n)... like keep the count of the of the numbers greater or smaller than k elements.....
hope it helps..

Hi,
The idea of finding the median of 2k elements is great but the problem is that both the arrays need not have k elements in them. This is where the algorithm fails. A solution to that could be to use binary search in each array to check if an element is the kth element. Checking if an element is the kth takes O(k) time since the kth element should have exactly k-1 elements less than it. It is easy to see that the number of elements less than A[i] in A[] is i. If it is the kth element in the combined array, it should have k-i-1 elements less than it in B[]. That is, B[k-i-1] should be < A[i] and B[k-i]>A[i].
This way, the solution requires a binary search on A[] and a binary search on B[].
Therefore it takes O(log(m) + log(n)) time, where m and n are the sizes of the 2 arrays.

merge the two arrays - but dont actually create a third array - rather keep track of index of this third array & return when you have decided what the kth element is.

Couldn't you do it in O(1)? Correct me if I am wrong. If you have 2 sorted arrays without duplicates if merged then, can't you just take each (ceiling(k/2) - 1) element and pick one? When k is even, you pick a greater one, otherwise you pick a smaller one. Actually you may apply this solution to any number of arrays as long as a global no duplicate condition is in effect.

Actually the solution suggested by xmagics sounds most promising. Can anyone explain the median finding algorithm ?
thanks,

alright!I will try to explain the median finding algorithm.
suppose A(10 elems) B(10 elems) and k==10
the mid index of A and B is 10/2 = 5
I assert than either A[ 5 ] or B[ 5 ] belongs to Top 10 elems. Because if you take m elems from A, you'll take 10-m elems from B.

so Min( A[ 5 ], B[ 5 ] ) belongs to Top 10 elems.
now we divide the original problem by half!we need find the Top 5 elems in A and B.
keep the median finding, it's log(k)
holp it helps.

I agreed with andy.

code:


m=k/2;n=k/2;t=k/2;

while (1)
if (a[m]<b[n-1])
{ m+=t/2;n-=t/2;t/=2;}
else if (a[m]>b[n+1])
{ m-=t/2;n+=t/2;t/=2;}
else break;
}
if (a[m]<b[n]) printf A[M];else printf B[N]

Thanks Andy, Mars. I think I get the idea..

Here is a reference to the perfect algorithm:

http://ocw.mit.edu/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/30C68118-E436-4FE3-8C79-6BAFBB07D935/0/ps9sol.pdf

Because we are trying to find the kth smallest number in the union of the arrays, all we have to do is find the median of the union of the first k of each array (total: 2k)

Because we are trying to find the kth smallest number in the union of the arrays, all we have to do is find the median of the union of the first k of each array (total: 2k)

call below function for A[0...k-1] and B[0...k-1] array - the median returned will be what we want: O(log k). // code is tested and works fine.


public static int find_median(int[] A, int[] B)
{
// A and B are sorted array with length n
int n = A.length;
int k = n/2;

int i = n/2-1;
int j = 0;

if(n%2 == 0)
j = n/2-1;
else
j = n/2;

while(true)
{
if(A[i] == B[j])
return A[i];
else if(A[i] < B[j])
{
if(A[i+1] >= B[j])
return B[j];
else
{
k = k/2;
i += k ;
j -= k;
}
}
else
{
if(B[j+1] >= A[i])
return A[i];
else
{
k = k/2;
i -= k ;
j += k;
}

}

}

}

Your biggest assumption is that A and B have equal length = n

Its wrong.

Keep two index i and j. one at the start of the first array and the 2nd at the start of the 2nd array. Increment i if a[i] < b[j] or else increment j. Do it k times. and you will get the desired num. This is O(k)

yeah its good like this but how would you find the median of two arrays of size n recursivly if its not to long??

yeah its good like this but how would you find the median of two arrays of size n recursivly if its not to long??

int[] a = { 2, 4, 5, 8, 9 };
int[] b = { 3, 7, 10, 12, 13 };
CASE 1: (k < a.length && k < b.length)
THEN
    if (a[k] < b[k]) {
                // n = numberOfElementsLessThan a[k] in b i.e. index of a[k] in b	        // n=binarySearch(a[k]) in b[0..k]
        	// find max between a[k-n] and b[n-1]
				max = a[k - n] > b[n - 1] ? a[k - n] : b[n - 1];
				System.out.println(max);
			} else {
             // n = numberOfElementsLessThan b[k] in a i.e. index of b[k] in a	        // n=binarySearch(b[k]) in a[0..k]
        	// find max between b[k-n] and a[n-1]
				max = b[k - n] > a[n - 1] ? b[k - n] : a[n - 1];
				System.out.println(max);
			}
The max value out of k-n +n-1 elements will be the k-1 th element i.e. kth smallest.

CASE 2: Similar logic may solve the remaining cases in logn

{{

internal static int FindKthNumber(int[] nums1, int[] nums2, int k)
{
if ((nums1 == null) || (nums1.Length == 0))
{
throw new ArgumentNullException("nums1");
}

if ((nums2 == null) || (nums2.Length == 0))
{
throw new ArgumentNullException("nums2");
}

if ((k <= 0)||(k > (nums1.Length + nums2.Length)))
{
throw new ArgumentOutOfRangeException("k");
}

return FindKthNumber(nums1,0,nums1.Length,nums2,0,nums2.Length,k);
}

private static int FindKthNumber(
int[] nums1,
int s1,
int l1,
int[] nums2,
int s2,
int l2,
int k)
{
if (l1 <= 0)
{
return nums2[k - 1];
}

if (l2 <= 0)
{
return nums1[k - 1];
}

if (k < 2)
{
return nums1[s1] < nums2[s2] ? nums1[s1] : nums2[s2];
}
else
{
count++;
int e1 = k / 2;
int e2 = k - e1;

if (e1 > l1)
{
e1 = l1;
e2 = k - e1;
}
else if (e2 > l2)
{
e2 = l2;
e1 = k - e2;
}

if (nums1[s1+e1 - 1] <= nums2[s2+e2 - 1])
{
return FindKthNumber(nums1, s1+e1, l1-e1, nums2, s2, l2, k - e1);
}
else
{
return FindKthNumber(nums1, s1, l1, nums2, s2+e2, l2-e2, k - e2);
}
}
}

}}

internal static int FindKthNumber(int[] nums1, int[] nums2, int k)
        {
            if ((nums1 == null) || (nums1.Length == 0))
            {
                throw new ArgumentNullException("nums1");
            }

            if ((nums2 == null) || (nums2.Length == 0))
            {
                throw new ArgumentNullException("nums2");
            }

            if ((k <= 0)||(k > (nums1.Length + nums2.Length)))
            {
                throw new ArgumentOutOfRangeException("k");
            }

            return FindKthNumber(nums1,0,nums1.Length,nums2,0,nums2.Length,k);
        }

        private static int FindKthNumber(
            int[] nums1,
            int s1, 
            int l1, 
            int[] nums2, 
            int s2, 
            int l2, 
            int k)
        {
            if (l1 <= 0)
            {
                return nums2[k - 1];
            }

            if (l2 <= 0)
            {
                return nums1[k - 1];
            }

            if (k < 2)
            {
                return nums1[s1] < nums2[s2] ? nums1[s1] : nums2[s2];
            }
            else
            {
                count++;
                int e1 = k / 2;
                int e2 = k - e1;

                if (e1 > l1)
                {
                    e1 = l1;
                    e2 = k - e1;
                }
                else if (e2 > l2)
                {
                    e2 = l2;
                    e1 = k - e2;
                }

                if (nums1[s1+e1 - 1] <= nums2[s2+e2 - 1])
                {
                    return FindKthNumber(nums1, s1+e1, l1-e1, nums2, s2, l2, k - e1);
                }
                else
                {
                    return FindKthNumber(nums1, s1, l1, nums2, s2+e2, l2-e2, k - e2);
                }
            }
        }

take first k/2 elem in both.

ifA[k/2] < B[k/2], numbers till A[k/2] ARE in the final array.

so the final array's k/2 to kth elements are present in B[0 to k/2] and A[k/2 to k]

now restart the comparisons for k/2 numbers for these arrays.

continue on eliminating half the numbers and finally you will have the kth number - handle edge cases correctly.

will someone explain the solution properly. I'm not able to figure out anything properly.

yaa.. right


http://supermanhelp.com

given two sorted array find algo for kth largest element in union o(logm+logn)

find(A, B, 0, K-1, 0, K-1, K)

find(A, B, beginA, endA, beginB, endB, k)
{
// end conditions...

if A[(beginA+endA)/2] > B[(beginB+endB)/2]
{
beginB = (beginB+endB)/2;
k -= (beginB+endB)/2;
find(A, B, beginA, endA, beginB, endB, k)
}
else if A[(beginA+endA)/2] < B[(beginB+endB)/2]
{
beginA = (beginA+endA)/2;
k -= (beginA+endA)/2;
find(A, B, beginA, endA, beginB, endB, k)
}
if A[(beginA+endA)/2] == B[(beginB+endB)/2]
{
...
}
}