The Kth element in the sorted arrays

source

Problem:

Easy: Given 2 sorted arrays of size n, give an efficient algorithm to find the kth largest number.

Solution:

Over here what we want is to manipulate cursors on the two arrays such that when their sum (total number of elements to their elements is k) The two arrays are such that all possible smallest elements in the kth array are left of the two cursors.

Code: (my attempt.. I think it works)

void findKthElement(int arr1[ ], int left1, iint arr2[ ], int left2, int k, int n) {
if ( k > 2n) return -1;
if (left1 + left2 + 2 == pos)
return (arr1[left1] > arr2[left1] ? arr1[left1] : arr2[left2])
else if (left1 + left2 + 2 <>
if (arr1[left1] <>
return (arr1, (left1 + n) / 2, arr2, left2 , k, n);
else
return (arr1, left1, arr2, (left2 + n) / 2, k, n);
else // move larger one left
if (arr1[left1] > arr2[left2])
return (arr1, (left1 + 0) / 2, arr2, left2 , k, n);
else
return (arr1, left1, arr2, (left2 + 0) / 2, k, n);
}

Hard: Given m sorted arrays of size n each, give an efficient algorithm to find the kth largest number.

Solution:

Pratik Poddar said...

@sumit. You raised an interesting point that the solution is independent of n. Your solution is correct. But I don't think its efficient.

@chera. Merging the "trimmed" arrays in O(mk) would solve the problem. But its not efficient. Interesting solution is your last comment! Thanks a lot.

Let me provide my algorithm. I think its more efficient for the easy part. You have two arrays A[1..k] and B[1..k]. The arrays are sorted. Compare A[k/2] and B[k/2]. If B[k/2]>A[k/2], we can remove all elements from B[k/2..k] and all elements from A[1..k/2]. So, we are left with two arrays of size k/2 and we need to find k/2th largest element (we need to take care of int.floor and int.ceiling but you get the idea).

For m=2, this algorithm would give the kth largest element in O(log k).

Can someone please generalize this for the general m case?

December 4, 2010 10:47 AM

Pratik Poddar said...One generalization that I can think of, works when m < (log k) - typical case in real world

Divide each array of size k into two halves. Get the centre points of all arrays. Find the minimum centre point. Except this array, remove the second half of the other m-1 arrays. So, we are left with (m-1) arrays of size k/2 each and one array of size k. And we need to find the kth largest element. This is like we have m+1 arrays of size k/2 each and we need to find the kth largest element. So, in each iteration, time taken is O(m), and we reduce the array size by half and increase the number of arrays by 1. Now I am not sure when to stop and how to calculate the complexity. But this looks like a reasonable approach.