Find Kth smallest element in two sorted arrays

Kth smallest element in two sorted arrays

Today, we will discuss a follow up problem to find kth smallest element in two sorted arrays. We have already have discussed how to find kth smallest element in one array : Find Kth smallest element : Application of quick sort

Given two sorted arrays, find Kth smallest element of union of 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.

Methods to find Kth smallest element in sorted array

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) extra space, where M and N are sizes of two sorted arrays. We may require only O(K) extra space if we keep track of number of elements sorted at the time of merging. Below is implementation of this method. 

#include <stdio.h>
 
int findMedian(int a[], int b[], int n, int m, int k){
    int i = 0, j = 0;
    int x = 0;
    int c[k];
 
    while(i<n && j<m){
        if(a[i] < b[j])
            c[x++] = a[i++];
        else
            c[x++] = b[j++];
 
        /* We have stored n+1 elements 0 to n
        Hence c[k-1] is n+1th element while 
        c[k-2] is nth element
        median = average of n and n+1 elements */
        if(x == k){
            return c[x-1];
        }
    }
 
    while(i<n){
        c[x++] = a[i++];
        if(x == k){
          return c[x-1];
        }
    }
 
    while(j<m){
        c[x++] = b[j++];
        if(x == k){
           return c[x-1];
        }
    }
}
 
int main(void) {
    int a[] = {10,20,30,50,60};
    int b[] = {70,80,90,100,110,120};
	int k = 9;
	// c = [10,20,30,50,60,70,80,90,10,110,120]
    int n =  sizeof(a)/sizeof(a[0]);
    int m =  sizeof(b)/sizeof(b[0]);
    printf("%dth smallest element in two arrays : %d", k,
            findMedian(a,b,n,m,k));
 
    return 0;
}

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

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.

Kth smallest element in two sorted arrays
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

#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 uniformity, 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 */
  int i =  min(sizeA, k/2) ; // K should be less than the size of array  
  int j =  min(sizeB, k/2) ; // K should be less than the size of array  
 
  if(a[i-1] > b[j-1])
    // Now we need to find only K-j th element
    return findKthSmallestElement(a, b+j, sizeA, (sizeB-j), k-j);
  else
    return findKthSmallestElement(a+i, b, (sizeA-i), sizeB, 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;
}

Test cases 

void testCases(){
     	//Test case 1 :
     	int a[] = {-37, 4, 7, 13, 29, 49, 50};
        int b[] = {-24, -14, 32 };

        int size_a  = sizeof(a)/sizeof(a[0]);
        int size_b  = sizeof(b)/sizeof(b[0]);
        if (find_kth(a,b,size_a, size_b, 5) == 7){
        	printf("Test case 1 Passed\n");
        }
        else{
        	printf("Test case 1 Failed\n");
        }
       
        
        int test_2_a[] = {10,30,40,50,60};
        int test_2_b[] = {30,50,100,110, 200};
        
        int test_2_size_a  = sizeof(test_2_a)/sizeof(test_2_a[0]);
        int test_2_size_b  = sizeof(test_2_b)/sizeof(test_2_b[0]);
        if (find_kth(test_2_a,test_2_b,test_2_size_a, test_2_size_b, 4) == 40){
        	printf("Test case 2 Passed\n");
        }
        else{
        	printf("Test case 2 Failed\n");
        }
        int test_3_a[] = {3,4,5,6,9,10};
        int test_3_b[] = {6,7,8,11,15,17,20,25};
        
        int test_3_size_a  = sizeof(test_3_a)/sizeof(test_3_a[0]);
        int test_3_size_b  = sizeof(test_3_b)/sizeof(test_3_b[0]);
        if (find_kth(test_3_a,test_3_b,test_3_size_a, test_3_size_b, 8) == 9){
        	printf("Test case 3 Passed\n" );
        }
        else{
        	printf("Test case 3 Failed\n");
        }
}

Let’s see how this code executes.

A = [3,4,5,6,9,10]
B = [6,7,8,11,15,17,20,25]
K = 8
Output = 9

In first call of findKthSmallestElement(), both array A and B are passed to it, with their respective sizes as findKthSmallestElement(A,B,6,8,8).

First condition in the function is to see what is relationship between two sizes. Function works on assumption that array is A smaller, and if size of array A is greater,swap arguments of functions, (where array B becomes A and A becomes B) and call function again with swapped arguments. This is to ensure that array  A is always smaller in function call. If this condition is false and move down.

Next, check if all the elements in smaller array, that is array A are done. (See that’s why swapped array above, so it is easier to see which is smaller array else we would have required two conditions here). If smaller array is processed, then return K-1 th element of the other array. Understand that here K is not the original K which was passed in first invocation.

In our current invocation, this condition is also false, hence, go down to next instruction.

Check if K ==1, that is also false. Now, find k/2th index of A and B. Call them i and j respectively. In this case i = 4 and j =4. Why?

i =  min(k/2, sizeA) = min(8/2, 6) = min(4,6) = 4
j =  min(k/2, sizeB) = min(8/2, 8) = min(4,8) = 4

Check if a[i-1] < b[j-1]? In this case, it is true that means all of k/2 elements of A will be less than k smallest elements and there may be more from right side of a[i]. Similarly, there will less elements from array b than k/2 in k smallest elements. Hence, look in right part of array A and left part of array B.

Now since we have already found i smallest elements, find k-i more elements to find kth smallest element. So function call will be findKthSmallestElement(a+i,b, (size_a-i) , j, k-i), here a+i represents array A after i elements from starts, and for array b we trimmed the size to j as right part is discarded. Concrete function call will be findKthSmallestElement(a+3,4, b, 3, 4, 5).

A = [6,9,10]
B = [6,7,8,11]

Function starts to execute from the top, first three conditions are false in this invocation also. Find i and j again.

i = min(k/2, sizeA) = min(5/2,3) = min(2,3) = 2
j = min(k/2, sizeB) = min(5/2,4) = min(2,4) = 2

Is a[i-1] < b[j-1]? This condition is false a[i-1]=9 and b[i-1]=7. This means all elements from array B from index 0 to j will be definitely part of k smallest elements, there may be more on right side of j. However, from array A, there will be less than i elements in k smallest elements.

Hence we will look in right part of array B and left part of array A. Call to function will be findKthSmallestElement(a, b+j, i, size_b-j, k-j), concrete invocation is findKthSmallestElement(a, b+2, 2,3, 3) .

A = [6,9]
B = [8,11]
K = 3

In this invocation, first three conditions are false. Come down to calculate i and j.

i = min(k/2, sizeA) = min(3/2,2) = min(1,2) = 1
j = min(k/2, sizeB) = min(3/2,3) = min(1,3) = 1

Is a[i-1] < b[j-1]? a[0]=6 is less than b[0]=7.  hence call will be findKthSmallestElement(a+i, b, (sizeA-i), j, k-i), concrete call for which is findKthSmallestElement(a+1,b, 1, 1, 2).

A = [9]
B = [8]

First three conditions are again false. Hence it comes down to calculate i and j again.

i = min(k/2, sizeA) = min(2/2,1) = min(1,1) = 1
j = min(k/2, sizeB) = min(2/2,1) = min(1,1) = 1

Is a[i-1] >  b[j-1]?  Which is true. Function call will be findKthSmallestElement(a, b+j, i, (sizeB-j),  k-j). Concrete call will be findKthSmallestElement(a, b+1, 1, 0, 1).

In the next invocation, a = {9} and b = {}. Since, size of A is less than size of B, function will be again invoked with swapped array, A = {} and B = {9}. Now, since k is equal to 1, return b[k-1] which is 9. Hence the Kth smallest element in union of these two sorted array is 9

Complexity of algorithm to find Kth smallest element in two sorted arrays is O(N+M).
If you have any good question or some algorithm, please send me across, I will share it for the wider community with due credits given to you. Remember sharing is caring. You can share this post!