# K-th element of 2 sorted array

Posted: 8 Feb, 2021

Difficulty: Hard

#### You are given two sorted arrays/list ‘arr1’ and ‘arr2’ and an integer k. You create a new sorted array by merging all the elements from ‘arr1’ and ‘arr2’. Your task is to find the kth smallest element of the merged array.

##### For example :

```
arr1= [2,3,45]
arr2= [4,6,7,8]
k= 4
The merged array will be :
[2,3,4,6,7,8,45]
The fourth element of this array will be 6 hence we return 6.
```

##### Input Format :

```
The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test cases follow.
The first line of each test case contains ‘m’ denoting the number of elements in arr1.
The second line of each test case contains ‘m’ space-separated integers denoting the elements of ‘arr1’.
The third line of each test case contains ‘n’ denoting the number of elements in arr2.
The fourth line of each test case contains ‘n’ space-separated integers denoting the elements of ‘arr2’.
The fifth line of each test case contains an integer ‘k’.
```

##### Output Format :

```
For each test case, return the kth element of the merged array.
Output for each test case will be printed in a new line.
```

##### Note :

```
You do not need to print anything; it has already been taken care of. Just implement the given function.
```

##### Constraints :

```
1 <= T <= 100
1 <= M <= 5000
1 <= N <= 5000
-10^9 <= arr1[i], arr2[i] <= 10^9
Where ‘T’ is the total number of test cases and M and N denote the size of 'arr1' and 'arr2'.
Elements in 'arr1' and 'arr2' will be sorted.
Time limit: 1 second
```

Approach 1

The key idea in solving this problem is to merge the 2 sorted arrays into a single sorted array and find its kth element.

The algorithm will be -

**We first make a new array arr3.**- We simultaneously traverse through both arr1 and arr2.
- Find the minimum element among the current two elements of both the arrays and update the arr3 with the least value and increment its index to the next position.
- Do this until one of the arrays is exhausted. Once exhausted take the other array and copy its elements in arr3.
- Finally, find the kth element of arr3 and return it.

Approach 2

The key idea in solving this problem is to use the divide and conquer approach i.e binary search on both the arrays to find the kth element.

The algorithm will be -

- Since the two arrays are sorted, we can safely assume that the k-th element in the merged array is either in the first k elements first array or in the first k elements in the second array.
- Now we take the middle element of both the arrays say mid1 and mid2.
- Now 2 cases arise:
- if mid1+mid2 is less than k, that means the kth element is in either the first half of array 1 or 2. This can be easily determined by comparing arr1[mid1] and arr2[mid2]
- If mid1+mid2 is not less than k, then the kth element is in the right half of the array1 or array 2.This can be easily determined by comparing arr1[mid1] and arr2[mid2]

Approach 3

The binary search approach for solving this problem can be further optimised. Instead of dividing the array in blocks of n/2 and m/2 we can divide it in blocks of k/2.

The algorithm will be -

- Since the two arrays are sorted, we can safely assume that the k-th element in the merged array is either in the first k elements first array or in the first k elements in the second array.
- We initialise x = k/2 and y = k/2 (we shall assume that arr1.length() <= k/2 and arr2.length() <= k/2. If the length of the array is too short, just take the whole length)
- In all explanation below, we shall assume that arr1[x] > arr2[y]
- Case 1: x + y = k
- If arr2[y+1] > arr1[x],arr1[x] is the answer.
- Otherwise, there are still many elements arr2[z], z > y, such that arr2[z] < arr1[x]. Therefore we increase y

- Case 2: x + y > k
- Since the sum exceeds k, we know that arr1[x] is an overestimate. So we decrease x

- Case 3: x + y < k
- If arr2[y+1] < arr1[x], this means there are many elements arr2[z], z > y, such that arr2[z] < arr1[x] that we have not accounted for. Therefore we increase y to account for them. Otherwise, we increase x

- Case 1: x + y = k

- Note that when we say mean increase/decrease, It means changing the value by k/4, k/8, k/16, etc after each iteration on each array. To illustrate this, suppose that you updated x 3 times and updated y 2 times. If you need to update x during the current iteration, you change x by k/16. If you need to update y during the current iteration, you change y by k/8.

SIMILAR PROBLEMS

# Game of 3

Posted: 11 Jul, 2021

Difficulty: Easy

# Lexicographic Permutation Rank

Posted: 13 Jul, 2021

Difficulty: Moderate

# Zero Pair Sum

Posted: 22 Jul, 2021

Difficulty: Moderate

# Implement a Queue

Posted: 27 Jul, 2021

Difficulty: Easy

# Remove K Corner Elements

Posted: 31 Jul, 2021

Difficulty: Easy