# 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 K^{th} 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.

## K^{th} 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.

## 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 K^{th} 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.