Find Kth smallest element in two sorted arrays

Find Kth smallest element in two sorted arrays

Today we will discuss a follow up problem of a problem which we have already solved in this post: Find Kth smallest element : Application of quick sort

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.

Analysis

One way of solving this 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) 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 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 the 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.

Kth smallest element in two sorted arrays
Find Kth smallest in two sorted arrays

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[K-1] and B[K-1] (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.

Code to find Kth smallest element in two sorted arrays

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

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