# K-th Element of Two Sorted Arrays

Given two sorted arrays of size m and n respectively, you are tasked with finding the element that would be at the k’th position of the final sorted array.

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
Since we are given two sorted arrays, we can use merging technique to get the final merged array. From this, we simply go to the k’th index.

## C++

 `// Program to find kth element from two sorted arrays ` `#include ` `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[5] = {2, 3, 6, 7, 9}; ` `    ``int` `arr2[4] = {1, 4, 8, 10}; ` `    ``int` `k = 5; ` `    ``cout << kth(arr1, arr2, 5, 4, k); ` `    ``return` `0; ` `}  `

/div>

## Java

 `// 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)); ` `    ``} ` `} ` ` `  `/* This code is contributed by Harsh Agarwal */`

## Python3

 `# Program to find kth element ` `# from two sorted arrays ` ` `  `def` `kth(arr1, arr2, m, n, k): ` `     `  `    ``sorted1 ``=` `[``0``] ``*` `(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)) ` ` `  `# This code is contributed by Smitha Dinesh Semwal `

## C#

 `// 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)); ` `} ` `} ` ` `  `// This code is contributed by mits  `

## PHP

 ` `

Output:

```6
```

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

Divide And Conquer Approach 1
While the previous method works, can we make our algorithm more efficient? The answer is yes. By using a divide and conquer approach, similar to the one used in binary search, we can attempt to find the k’th element in a more efficient way.

```Explanation:
We compare the middle elements of arrays arr1 and arr2,
let us call these indices mid1 and mid2 respectively.

Let us assume arr1[mid1]  k, then clearly the elements after
mid2 cannot be the required element. We then set the last
element of arr2 to be arr2[mid2].

In this way, we define a new subproblem with half the size
of one of the arrays.
```

## C++

 `// Program to find k-th element from two sorted arrays ` `#include ` `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[5] = {2, 3, 6, 7, 9}; ` `    ``int` `arr2[4] = {1, 4, 8, 10}; ` ` `  `    ``int` `k = 5; ` `    ``cout << kth(arr1, arr2, arr1 + 5, arr2 + 4,  k - 1); ` `    ``return` `0; ` `}  `

Output:

```6
```

Note that in the above code, k is 0 indexed, which means if we want a k that’s 1 indexed, we have to subtract 1 when passing it to the function.
Time Complexity: O(log n + log m)

Divide And Conquer Approach 2
While the above implementation is very efficient, we can still get away with making it more efficient. Instead of dividing the array into segments of n / 2 and m / 2 then recursing, we can divide them both by k / 2 and recurse. Below implementation displays this.

```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[1]

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

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

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

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

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[1] < arr2[1]
Hence, arr1[1] = 6 is the answer.
```

## C++

 `// Program to find kth element from two sorted arrays ` `#include ` `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[5] = {2, 3, 6, 7, 9}; ` `    ``int` `arr2[4] = {1, 4, 8, 10}; ` ` `  `    ``int` `k = 5; ` `    ``cout << kth(arr1, arr2, 5, 4,  k); ` `    ``return` `0; ` `} `

## Java

 `// 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)); ` `    ``} ` `}  ` ` `  `// This code is contributed by 29AjayKumar `

## C#

 `// 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)); ` `    ``} ` `} ` ` `  `// This code is contributed by PrinciRaj1992 `

Output:

```6
```

Time Complexity: O(log k)

Now, k can take a maximum value of m + n. This means that log k can be in the worst case, log(m + n). Logm + logn = log(mn) by properties of logarithms, and when m, n > 2, log(m + n) < log(mn). Thus this algorithm slightly outperforms the previous algorithm.Also see another simple implemented log k approach suggested by Raj Kumar.

## C++

 `// C++ Program to find kth element from two sorted arrays ` `// Time Complexity: O(log k) ` ` `  `#include ` `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[0], arr2[0]); ` `   `  `  ``// 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[5] = {2, 3, 6, 7, 9}; ` `    ``int` `arr2[4] = {1, 4, 8, 10}; ` `    ``int` `m = ``sizeof``(arr1)/``sizeof``(arr1[0]); ` `    ``int` `n = ``sizeof``(arr2)/``sizeof``(arr2[0]); ` `    ``int` `k = 5; ` `     `  `    ``int` `ans = kth(arr1,m,arr2, n, k); ` `     `  `    ``if``(ans == -1) cout<<``"Invalid query"``; ` `    ``else` `cout<

Time Complexity:O(log k)

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.