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.
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.
|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).