Find Kth smallest element in two sorted arrays

Find Kth smallest element in two sorted arrays

Earlier on this blog, we discussed a problem where, we found K smallest elements in a array. There are different ways to do, like sorting the array and take first K elements, or optimized quick sort, or using min heap. Detailed explanation for all methods is discussed here at Find K smallest elements in array.

Today, our problem is to find Kth smallest element in two sorted arrays. In another words, given two sorted arrays, find Kth smallest element of union of these two arrays.

For example if A = [10, 20, 40, 60] and B =[15, 35, 50, 70, 100] and K = 4 then solution should be 35 because union of above arrays will be C = [10,15,20,35,40,50,60,70,100] and fourth smallest element is 35.

Kth smallest element in two sorted arrays : analysis

One way of solving problem is merging both arrays into one sorted array and then return the Kth smallest element of merged array. This will require O(M+N) additional space. Also, complexity of sorting will be O((M+N)log(M+N)) where M and N are sizes of two sorted arrays. Can we do better than this? Do we need to completely merge two arrays or based on some information at hand at point any point of time, we can discard some portion of arrays?

Discard. This word rings bells, divide and  conquer 🙂 How can we apply that here is the next question.  Find K/2th index from first array, call it i and K/2th index from second, call it j.  Now consider this:

1.If A[i] > B[j],then Kth smallest element will include elements more than K/2 elements from array B and less than K/2 elements from array A. So our area of searching reduces to left part of K/2 index in array A and right part of k/2 index in array B, as shown in figure below.
Again, since we have already found j definite smallest elements, we will reduce the search for (k-j)th smallest element in reduced search space.

2. Similarly, if A[i] < B[j], our search space reduces to right part of K/2 index in array A and left of K/2 elements of array B, as shown in figure below. Again since we have already found i definite smallest elements, we will reduce the search for (k-i)th smallest element in reduced search space.

So what will be the base case: When K is one, then we return the minimum of A[i] and B[j] (considering the zero based indexing of array) or if one of the array becomes null then return the other array's Kth smallest element.
OK, we are all set to code now. It's really simple.

Kth-smallest-element-in-sorted-arrays

Code to find Kth smallest element in two sorted arrays

#include <stdio.h>

#define min(a,b) a > b ? b:a

int findKthSmallestElement(int a[], int b[],
       int sizeA, int sizeB, int k){
  /* to maintain uniformaty, we will assume 
  that size_a is smaller than size_b
  else we will swap array in call */
  if(sizeA > sizeB)
    return findKthSmallestElement(b, a, sizeB, sizeA, k);

  /* Now case when size of smaller array is 0 
    i.e there is no elemt in one array*/
  if(sizeA == 0 && sizeB >0)
    return b[k-1]; // due to zero based index
  
  /* case where K ==1 that means we have hit limit */
  if(k ==1)
    return min(a[0], b[0]);

  /* Now the divide and conquer part */
  // K should be less than the size of array  
  int i =  min(sizeA, k/2) ;
  // K should be less than the size of array   
  int j =  min(sizeB, k/2) ; 

  if(a[i-1] > b[j-1])
    // Now we need to find only K-j th element
    return findKthSmallestElement(a, b+j, i, (sizeB-j), k-j);
  else
    return findKthSmallestElement(a+i, b, (sizeA-i), j, k-i);

  return -1;
}
int main(){
  int a[] = {10,30,40,50,60};
  int b[] = {30,50,100,110, 200};

  int sizeA  = sizeof(a)/sizeof(a[0]);
  int sizeB  = sizeof(b)/sizeof(b[0]);

  printf("\n Kth smallest element is : %d",
         findKthSmallestElement(a,b,sizeA, sizeB, 4));
  return 0;
}

Complexity of algorithm to find Kth smallest element in union of two arrays is O(log(N+M)).

Please share if there is something wrong or missing. we would be glad to hear from you.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s