K-th smallest element of two sorted arrays

In this article, we have explored algorithms to find the K-th smallest element of two sorted arrays. This involve the idea of Binary Search.

Table of contents:

1. Basic approach to find K-th smallest element of two sorted arrays.
2. Improved approach by reducing space complexity to constant.
3. Further improved approaches

Pre-requisites

• Array
• Binary search

Introduction

In this article, we will learn various methods to find the kth smallest element of two arrays. We have multiple ways to solve the problem, but we move from a fundamental to an optimized approach. So our task is to find out the kth position of the final sorted array.

Naïve approach

Steps:

1. Firstly we take the given arrays and form a new merged array. To sort the array, we take an element that is lesser from two arrays each time.
2. If elements are leftover in either the first or second array, we finally copy those elements in the new merged array.
3. As we want an element at position k (k-1 index), we return that element.

Input:

//finding kth element of sorted array
#include <iostream>
using namespace std;

int element_at_K(int arr1[], int arr2[], int a, int b, int k)
{
	int final_array[a + b];
	int i = 0, j = 0, c = 0;
	while (i < a && j < b)
	{
		if (arr1[i] < arr2[j])
			final_array[c++] = arr1[i++];
		else
			final_array[c++] = arr2[j++];
	}
	while (i < a)
	    final_array[c++] = arr1[i++];
	while (j < b)
		final_array[c++] = arr2[j++];
	return final_array[k - 1]; //as we need element at kth position
}

int main()
{
	int arr1[9] = {2, 4, 8, 10, 12, 34, 67, 81, 90};
	int arr2[5] = {2, 3, 8, 13, 19};
	int k = 8;
	cout << element_at_K(arr1, arr2, 9, 5, k);
	return 0;
}

Output:

12
--------------------------------
Process exited after 0.08281 seconds with return value 0
Press any key to continue . . . 

Observation:
Time complexity:
We traverse the given arrays once and then find out a kth element from sorted array time complexity would be O(N).
Space complexity:
We are using extra space to store elements of the given two arrays. As the size of the first array is a and the second array is b total space complexity would be O(a+b).

2nd approach without using extra space

We came up with this approach to reduce the space we are using to store the merged array.

1. we search the element at the kth position by incrementing the counter value from zero every time and finally returning the value when the counter reaches the required k value.

Implementation:

//finding kth element of sorted array without using extra space
#include <bits/stdc++.h>
using namespace std;

int element_at_K(int A1[], int A2[], int m,
		int n, int k)
{
	int count = 0, i = 0, j = 0;

	//taking lesser element each time and incrementing counter
	while(i < m && j < n)
	{
		if(A1[i] < A2[j])
		{
			count++;
			if(count == k)
				return A1[i];
			i++;
		}
		else
		{
			count++;
			if(count == k)
				return A2[j];
			j++;
		}
	}

	//if all elements in an array A2 is completed
	while(i < m)
	{
		count++;
		if(count == k)
			return A1[i];
		i++;
	}

	//if all elements in an array A1 is completed
	while(j < n)
	{
		count++;
		if(count == k)
			return A2[j];
		j++;
	}
}

int main()
{
	int A1[9] = {2, 4, 8, 10, 12, 34, 67, 81, 90};
	int A2[5] = {2, 3, 8, 13, 19};
	int k = 8;
	cout << element_at_K(A1, A2, 9, 5, k);
	return 0;

}

Output:

12
--------------------------------
Process exited after 0.07094 seconds with return value 0
Press any key to continue . . . 

Suggestion: Please try to dry run the code to understand better.
Observation:
Time complexity:
As we traverse only k elements time complexity will be O(k) (Time complexity has been improved)
Space complexity:
We are not using extra space for the sorted array hence space complexity is constant that is O(1)

Optimized approach:

Similar to binary search we will try to compare middle elements of array 1 and array 2. Here instead of traversing whole array we try to divide the array into n/2 and m/2 respectively and using recursion.

Steps:

1. We check the base conditions. If any of the given arrays is empty, we directly find the kth element of the non-empty array.
2. We find the mid values of each array and if sum of index of mid values is less than k, we check for which collection of mid is greater. If 1st array mid is greater, we eliminate first part of array 2 and vice versa.
3. If sum of index of mid values is greater than or equal to k and mid of 1st array is greater then second half of first will no longer be included in our solution. And if mid value of arary 2 is greater second half of second array will be excluded.

Implementation:

#include <iostream>
using namespace std;

int kth(int *arrA, int *arrB, int *endA, int *endB, int k)
{
	if (arrA == endA) //if they gave an array A which is empty then we directlr return kth element of array B
		return arrB[k];
	if (arrB == endB)  //if they gave an array A which is empty then we directlr return kth element of array B
		return arrA[k];
	int midA = (endA - arrA) / 2;
	int midB = (endB - arrB) / 2;
	if (midA + midB < k)   //if sumof index values of mid less than k
	{
		if (arrA[midA] > arrB[midB])
			return kth(arrA, arrB + midB + 1, endA, endB,
				k - midB - 1);
		else
			return kth(arrA + midA + 1, arrB, endA, endB,
				k - midA - 1);
	}
	else ////if sumof index values of mid greaterthan or equal to k
	{
		if (arrA[midA] > arrB[midB])
			return kth(arrA, arrB, arrA + midA, endB, k);
		else
			return kth(arrA, arrB, endA, arrB + midB, k);
	}
}

int main()
{
	int arrA[7] = {1, 4, 7, 9, 10, 11, 12};
	int arrB[4] = {1, 5, 7, 15};

	int k = 5;
	cout << kth(arrA, arrB, arrA + 5, arrB + 4, k - 1);
	return 0;
}

Output:

7
--------------------------------
Process exited after 0.08913 seconds with return value 0
Press any key to continue . . .

Observation:
Time complexity:
O(logn+logm), we have logarithmic time complexity because we divide the arrays each time we execute the function.
Space complexity:
Constant O(1)
Is it possible to further optimize the code?
Yes, we can still improve the time complexity

Further optimized version:

We will always try to do the first array as a smaller array so that time complexity will reduce and binary search takes place in a shorter space.

Steps:

1. Here, the given two arrays are partitioned so that some element goes to the left part of the merged array and the remaining goes to the right half similarly, the second array.
2. We know the suitable condition is l1<=r2 and l2<=r1.
3. Take low value, which is max(0,k-m) that takes at least one element from array one, and min(k,n) represents we can handle all aspects from a single array.
4. We find cut1 and cut2. And then assigning values to l1,l2, and r1,r2 (If there are no elements in the left part, we take l1 and l2 a minimum value, and if all elements are in the right part we take r1 and r2 a maximum value)
5. If the above condition is not satisfied, we try to cut the array at a different index accordingly.
6. Now, we get a sorted merged array by checking the above conditions and printing the element at position k.

Input:

#include <iostream>
using namespace std;
int kth(int arr1[], int arr2[], int n, int m, int k){
	if(n>m){
		return kth(arr2,arr1,m,n,k);
	}
	int l=max(0,k-m), h=min(k,n);
	while(l<=h) {
		int cut1=(l+h)/2;
		int cut2=k-cut1;
		int l1=cut1==0 ? INT_MIN:arr1[cut1-1];
		int l2=cut2==0 ? INT_MIN:arr2[cut2-1];
		int r1=cut1==n ? INT_MAX:arr1[cut1];
		int r2=cut2==n ? INT_MAX:arr2[cut2];
		if(l1<=r2 && l2<=r2)
		return max(l1,l2);
		else if(l1>r2)
		h=cut1-1;
		else
		l=cut1+1;
		
		return 1;
		
	}
}

int main()
{
	int arr1[6] = {1, 4, 7, 9, 10, 11};
	int arr2[4] = {1, 5, 7, 15};

	int k = 5;
	cout << kth(arr1, arr2, 6, 4, k);
	return 0;
}

Output:

7
--------------------------------
Process exited after 0.06657 seconds with return value 0
Press any key to continue . . .

Example

Here we will try to learn how the above code is working by taking an example.
arr1[6] = {1, 4, 7, 9, 10, 11};
arr2[4] = {1, 5, 7, 15};
As we have taken size of array is larger to reduce
time complexity we interchange arr1 and aar2 as discussed
above.We caluculate the values l=1,h=5,cut1=3,cut2=2 we iterate through the process until we reach condition l1<=r2 and l2<=r1.The point at which we get l1=7, l2=5 and r1=9, r2=7 loop ends and it return max(l1,l2)==7.
Observation:
Time complexity:
O(log(min(m,n))
Space complexity:
O(1)
Resources: Please watch this video to understand the above method better.

With this article at OpenGenus, you must have the complete idea of how to find K-th smallest element of two sorted arrays.