Last Updated: 8 Feb, 2021
K-th Element of Two Sorted Arrays
Hard
Asked in companies
You're given two sorted arrays 'arr1' and 'arr2' of size 'n' and 'm' respectively and an element 'k'.
Find the element that would be at the 'kth' position of the combined sorted array.
Position 'k' is given according to 1 - based indexing, but arrays 'arr1' and 'arr2' are using 0 - based indexing.
For example :
Input: 'arr1' = [2, 3, 45], 'arr2' = [4, 6, 7, 8] and 'k' = 4
Output: 6
Explanation: The merged array will be [2, 3, 4, 6, 7, 8, 45]. The element at position '4' of this array is 6. Hence we return 6.
Input Format :
The first line contains ‘n’ denoting the number of elements in ‘arr1’.
The second line contains ‘n’ space-separated integers denoting the elements of ‘arr1’.
The third line contains ‘m’ denoting the number of elements in ‘arr2’.
The fourth line contains ‘m’ space-separated integers denoting the elements of ‘arr2’.
The fifth line contains an integer ‘k’.
Output Format :
Return the 'kth' element of the combined sorted array.
Note :
You do not need to print anything; it has already been taken care of. Just implement the given function.
Approaches
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.
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]’
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