K-th element of 2 sorted array

Posted: 8 Feb, 2021
Difficulty: Hard

PROBLEM STATEMENT

Try Problem

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.
Try Problem