# Kth Smallest Element in Two Sorted Arrays

0
159

## K-th Element of Two Sorted Arrays

In this post, You can easily learn kth smallest element in two sorted arrays. You must identify the element that would be at the kth position of the final sorted array given two sorted arrays of size m and n, respectively.

Examples:

``````Input : Array 1 - 2 3 6 7 9
Array 2 - 1 4 8 10
k = 5
Output : 6
Explanation: The final sorted array would be -
1, 2, 3, 4, 6, 7, 8, 9, 10
The 5th element of this array is 6.
Input : Array 1 - 100 112 256 349 770
Array 2 - 72 86 113 119 265 445 892
k = 7
Output : 256
Explanation: Final sorted array is -
72, 86, 100, 112, 113, 119, 256, 265, 349, 445, 770, 892
7th element of this array is 256.``````

Basic Approach

We can utilize the merging procedure to retrieve the final merged array because we have two sorted arrays. We simply go to the k’th index from here.

### C++ Programe to Find kth Element from Two Sorted Arrays

``````
// Program to find kth element from two sorted arrays
#include <iostream>
using namespace std;

int kth(int arr1[], int arr2[], int m, int n, int k)
{
int sorted1[m + n];
int i = 0, j = 0, d = 0;
while (i < m && j < n)
{
if (arr1[i] < arr2[j])
sorted1[d++] = arr1[i++];
else
sorted1[d++] = arr2[j++];
}
while (i < m)
sorted1[d++] = arr1[i++];
while (j < n)
sorted1[d++] = arr2[j++];
return sorted1[k - 1];
}

int main()
{
int arr1 = {2, 3, 6, 7, 9};
int arr2 = {1, 4, 8, 10};
int k = 5;
cout << kth(arr1, arr2, 5, 4, k);
return 0;
}  ``````

### Java Program to Find kth Element from Two Sorted Arrays

``````
// Java Program to find kth element
// from two sorted arrays

class Main
{
static int kth(int arr1[], int arr2[], int m, int n, int k)
{
int[] sorted1 = new int[m + n];
int i = 0, j = 0, d = 0;
while (i < m && j < n)
{
if (arr1[i] < arr2[j])
sorted1[d++] = arr1[i++];
else
sorted1[d++] = arr2[j++];
}
while (i < m)
sorted1[d++] = arr1[i++];
while (j < n)
sorted1[d++] = arr2[j++];
return sorted1[k - 1];
}

// main function
public static void main (String[] args)
{
int arr1[] = {2, 3, 6, 7, 9};
int arr2[] = {1, 4, 8, 10};
int k = 5;
System.out.print(kth(arr1, arr2, 5, 4, k));
}
}
``````

### Python 3 Program to Find kth Element from Two Sorted Arrays

``````
# Program to find kth element
# from two sorted arrays

def kth(arr1, arr2, m, n, k):

sorted1 =  * (m + n)
i = 0
j = 0
d = 0
while (i < m and j < n):

if (arr1[i] < arr2[j]):
sorted1[d] = arr1[i]
i += 1
else:
sorted1[d] = arr2[j]
j += 1
d += 1

while (i < m):
sorted1[d] = arr1[i]
d += 1
i += 1
while (j < n):
sorted1[d] = arr2[j]
d += 1
j += 1
return sorted1[k - 1]

# driver code
arr1 = [2, 3, 6, 7, 9]
arr2 = [1, 4, 8, 10]
k = 5;
print(kth(arr1, arr2, 5, 4, k))
``````

### C# Program to Find kth Element from Two Sorted Arrays

``````
// C# Program to find kth element
// from two sorted arrays
class GFG
{
static int kth(int[] arr1, int[] arr2,
int m, int n, int k)
{
int[] sorted1 = new int[m + n];
int i = 0, j = 0, d = 0;
while (i < m && j < n)
{
if (arr1[i] < arr2[j])
sorted1[d++] = arr1[i++];
else
sorted1[d++] = arr2[j++];
}
while (i < m)
sorted1[d++] = arr1[i++];
while (j < n)
sorted1[d++] = arr2[j++];
return sorted1[k - 1];
}

// Driver Code
static void Main()
{
int[] arr1 = {2, 3, 6, 7, 9};
int[] arr2 = {1, 4, 8, 10};
int k = 5;
System.Console.WriteLine(kth(arr1, arr2,
5, 4, k));
}
} ``````

### PHP Program to Find kth Element from Two Sorted Arrays

``````
<?php
// Program to find kth
// element from two
// sorted arrays

function kth(\$arr1, \$arr2,
\$m, \$n, \$k)
{
\$sorted1[\$m + \$n] = 0;
\$i = 0;
\$j = 0;
\$d = 0;
while (\$i < \$m && \$j < \$n)
{
if (\$arr1[\$i] < \$arr2[\$j])
\$sorted1[\$d++] = \$arr1[\$i++];
else
\$sorted1[\$d++] = \$arr2[\$j++];
}
while (\$i < \$m)
\$sorted1[\$d++] = \$arr1[\$i++];
while (\$j < \$n)
\$sorted1[\$d++] = \$arr2[\$j++];
return \$sorted1[\$k - 1];
}

// Driver Code
\$arr1 = array(2, 3, 6, 7, 9);
\$arr2 = array(1, 4, 8, 10);
\$k = 5;
echo kth(\$arr1, \$arr2, 5, 4, \$k); ``````

### Output:

``````6
Time Complexity: O(n)
Auxiliary Space : O(m + n)

Divide And Conquer Approach 1``````

Can we make our algorithm more efficient while using the previous method? Yes, it is correct. We can try to identify the k’th element more efficiently by utilizing a divide and conquer strategy, similar to the one used in binary search.

``````We compare the middle elements of arrays arr1 and arr2, which we'll refer to as mid1 and mid2 indices.

If arr1[mid1] k, then the elements after mid2 definitely cannot be the needed element. The last element of arr2 is then set to arr2[mid2].

As a result, a new subproblem with half the size of one of the arrays is defined.``````

### C++ Program to Find kth Element from Two Sorted Arrays

``````
// Program to find k-th element from two sorted arrays
#include <iostream>
using namespace std;

int kth(int *arr1, int *arr2, int *end1, int *end2, int k)
{
if (arr1 == end1)
return arr2[k];
if (arr2 == end2)
return arr1[k];
int mid1 = (end1 - arr1) / 2;
int mid2 = (end2 - arr2) / 2;
if (mid1 + mid2 < k)
{
if (arr1[mid1] > arr2[mid2])
return kth(arr1, arr2 + mid2 + 1, end1, end2,
k - mid2 - 1);
else
return kth(arr1 + mid1 + 1, arr2, end1, end2,
k - mid1 - 1);
}
else
{
if (arr1[mid1] > arr2[mid2])
return kth(arr1, arr2, arr1 + mid1, end2, k);
else
return kth(arr1, arr2, end1, arr2 + mid2, k);
}
}

int main()
{
int arr1 = {2, 3, 6, 7, 9};
int arr2 = {1, 4, 8, 10};

int k = 5;
cout << kth(arr1, arr2, arr1 + 5, arr2 + 4,  k - 1);
return 0;
}  ``````

### Output:

``6``

Note that k is indexed 0 in the preceding code, thus if we want a 1 indexed k, we must remove 1 before providing it to the function.
O(log n + log m) is the time complexity.

### Divide And Conquer Approach 2

While the preceding approach is quite efficient, there is always room for improvement. Rather than partitioning the array into n / 2 and m / 2 parts and recursing, we can divide them both by k / 2 and recurse. This is shown in the implementation below.

``````Explanation:
Instead of comparing the middle element of the arrays,
we compare the k / 2th element.
Let arr1 and arr2 be the arrays.
Now, if arr1[k / 2]  arr1

New subproblem:
Array 1 - 6 7 9
Array 2 - 1 4 8 10
k = 5 - 2 = 3

floor(k / 2) = 1
arr1 = 6
arr2 = 1
arr1 > arr2

New subproblem:
Array 1 - 6 7 9
Array 2 - 4 8 10
k = 3 - 1 = 2

floor(k / 2) = 1
arr1 = 6
arr2 = 4
arr1 > arr2

New subproblem:
Array 1 - 6 7 9
Array 2 - 8 10
k = 2 - 1 = 1

Now, we directly compare first elements,
since k = 1.
arr1 < arr2
Hence, arr1 = 6 is the answer.``````

### C++ Program to Find kth Element from Two Sorted Arrays

``````// Program to find kth element from two sorted arrays
#include <iostream>
using namespace std;

int kth(int arr1[], int arr2[], int m, int n, int k,
int st1 = 0, int st2 = 0)
{
// In case we have reached end of array 1
if (st1 == m)
return arr2[st2 + k - 1];

// In case we have reached end of array 2
if (st2 == n)
return arr1[st1 + k - 1];

// k should never reach 0 or exceed sizes
// of arrays
if (k == 0 || k > (m - st1) + (n - st2))
return -1;

// Compare first elements of arrays and return
if (k == 1)
return (arr1[st1] < arr2[st2]) ?
arr1[st1] : arr2[st2];
int curr = k / 2;

// Size of array 1 is less than k / 2
if (curr - 1 >= m - st1)
{
// Last element of array 1 is not kth
// We can directly return the (k - m)th
// element in array 2
if (arr1[m - 1] < arr2[st2 + curr - 1])
return arr2[st2 + (k - (m - st1) - 1)];
else
return kth(arr1, arr2, m, n, k - curr,
st1, st2 + curr);
}

// Size of array 2 is less than k / 2
if (curr-1 >= n-st2)
{
if (arr2[n - 1] < arr1[st1 + curr - 1])
return arr1[st1 + (k - (n - st2) - 1)];
else
return kth(arr1, arr2, m, n, k - curr,
st1 + curr, st2);
}
else
{
// Normal comparison, move starting index
// of one array k / 2 to the right
if (arr1[curr + st1 - 1] < arr2[curr + st2 - 1])
return kth(arr1, arr2, m, n, k - curr,
st1 + curr, st2);
else
return kth(arr1, arr2, m, n, k - curr,
st1, st2 + curr);
}
}

// Driver code
int main()
{
int arr1 = {2, 3, 6, 7, 9};
int arr2 = {1, 4, 8, 10};

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

### Java Program to Find kth Element from Two Sorted Arrays

``````
// Java Program to find kth element from two sorted arrays
class GFG
{

static int kth(int arr1[], int arr2[], int m,
int n, int k, int st1, int st2)
{
// In case we have reached end of array 1
if (st1 == m)
{
return arr2[st2 + k - 1];
}

// In case we have reached end of array 2
if (st2 == n)
{
return arr1[st1 + k - 1];
}

// k should never reach 0 or exceed sizes
// of arrays
if (k == 0 || k > (m - st1) + (n - st2))
{
return -1;
}

// Compare first elements of arrays and return
if (k == 1)
{
return (arr1[st1] < arr2[st2])
? arr1[st1] : arr2[st2];
}
int curr = k / 2;

// Size of array 1 is less than k / 2
if (curr - 1 >= m - st1)
{

// Last element of array 1 is not kth
// We can directly return the (k - m)th
// element in array 2
if (arr1[m - 1] < arr2[st2 + curr - 1])
{
return arr2[st2 + (k - (m - st1) - 1)];
}
else
{
return kth(arr1, arr2, m, n, k - curr,
st1, st2 + curr);
}
}

// Size of array 2 is less than k / 2
if (curr - 1 >= n - st2)
{
if (arr2[n - 1] < arr1[st1 + curr - 1])
{
return arr1[st1 + (k - (n - st2) - 1)];
}
else
{
return kth(arr1, arr2, m, n, k - curr,
st1 + curr, st2);
}
}
else

// Normal comparison, move starting index
// of one array k / 2 to the right
if (arr1[curr + st1 - 1] < arr2[curr + st2 - 1])
{
return kth(arr1, arr2, m, n, k - curr,
st1 + curr, st2);
}
else
{
return kth(arr1, arr2, m, n, k - curr,
st1, st2 + curr);
}
}

// Driver code
public static void main(String[] args)
{
int arr1[] = {2, 3, 6, 7, 9};
int arr2[] = {1, 4, 8, 10};
int k = 5;
int st1 = 0, st2 = 0;
System.out.println(kth(arr1, arr2, 5, 4, k, st1, st2));
}
}
``````

### C# Program to Find kth Element from Two Sorted Arrays

``````
// C# Program to find kth element from two sorted arrays
using System;

class GFG
{

static int kth(int []arr1, int []arr2, int m,
int n, int k, int st1, int st2)
{
// In case we have reached end of array 1
if (st1 == m)
{
return arr2[st2 + k - 1];
}

// In case we have reached end of array 2
if (st2 == n)
{
return arr1[st1 + k - 1];
}

// k should never reach 0 or exceed sizes
// of arrays
if (k == 0 || k > (m - st1) + (n - st2))
{
return -1;
}

// Compare first elements of arrays and return
if (k == 1)
{
return (arr1[st1] < arr2[st2])
? arr1[st1] : arr2[st2];
}
int curr = k / 2;

// Size of array 1 is less than k / 2
if (curr - 1 >= m - st1)
{

// Last element of array 1 is not kth
// We can directly return the (k - m)th
// element in array 2
if (arr1[m - 1] < arr2[st2 + curr - 1])
{
return arr2[st2 + (k - (m - st1) - 1)];
}
else
{
return kth(arr1, arr2, m, n, k - curr,
st1, st2 + curr);
}
}

// Size of array 2 is less than k / 2
if (curr - 1 >= n - st2)
{
if (arr2[n - 1] < arr1[st1 + curr - 1])
{
return arr1[st1 + (k - (n - st2) - 1)];
}
else
{
return kth(arr1, arr2, m, n, k - curr,
st1 + curr, st2);
}
}
else

// Normal comparison, move starting index
// of one array k / 2 to the right
if (arr1[curr + st1 - 1] < arr2[curr + st2 - 1])
{
return kth(arr1, arr2, m, n, k - curr,
st1 + curr, st2);
}
else
{
return kth(arr1, arr2, m, n, k - curr,
st1, st2 + curr);
}
}

// Driver code
public static void Main(String[] args)
{
int []arr1 = {2, 3, 6, 7, 9};
int []arr2 = {1, 4, 8, 10};
int k = 5;
int st1 = 0, st2 = 0;
Console.WriteLine(kth(arr1, arr2, 5, 4, k, st1, st2));
}
}
``````

### Output:

``6``

Complexity of Time: O (log k)

k can now take on the maximum value of m + n. This suggests that log k might be log(m + n) in the worst-case scenario. Logm + logn = log(mn) by logarithm properties, and log(m + n) log(m + n) log(m + n) log(m + n) log(m + n) log(m + n) log(m + n) log(m + n) log(m + n) log(m (mn). As a result, this approach outperforms the previous algorithm by a little margin. Also, have a look at another log k approach that is straightforward to implement.

### C++ Program to Find kth Element from Two Sorted Arrays

``````// C++ Program to find kth element from two sorted arrays
// Time Complexity: O(log k)

#include <iostream>
using namespace std;

int kth(int arr1[], int m, int arr2[], int n, int k)
{

if (k > (m+n) || k < 1) return -1;

// let m <= n
if (m > n) return kth(arr2, n, arr1, m, k);

// if arr1 is empty returning k-th element of arr2
if (m == 0) return arr2[k - 1];

// if k = 1 return minimum of first two elements of both arrays
if (k == 1) return min(arr1, arr2);

// now the divide and conquer part
int i = min(m, k / 2), j = min(n, k / 2);

if (arr1[i - 1] > arr2[j - 1] )
// Now we need to find only k-j th element since we have found out the lowest j
return kth(arr1, m, arr2 + j, n - j, k - j);
else
// Now we need to find only k-i th element since we have found out the lowest i
return kth(arr1 + i, m - i, arr2, n, k - i);
}

// Driver code
int main()
{
int arr1 = {2, 3, 6, 7, 9};
int arr2 = {1, 4, 8, 10};
int m = sizeof(arr1)/sizeof(arr1);
int n = sizeof(arr2)/sizeof(arr2);
int k = 5;

int ans = kth(arr1,m,arr2, n, k);

if(ans == -1) cout<<"Invalid query";
else cout<<ans;

return 0;
} ``````

Time Complexity:O(log k)

Latest Article:

How to find the kth smallest element in the union of two sorted arrays?