Kth Element of Two Sorted Arrays

Hard
0/120
Average time to solve is 10m
99 upvotes
Asked in companies
AdobeAmazonGoldman Sachs

Problem statement

Ninja wants to serve food to needy people. So, he bought Ladoos from a sweet shop and placed them on plates. There can be any number of Ladoos present in a plate.

Plates containing Ladoos are placed in two rows. Each row is sorted in increasing order by the number of Ladoos in a plate.

For example : 
‘ROW1’ :  [2, 5, 8, 17] and  ‘ROW2’ :  [1, 4, 8, 13, 20]

Now people come one by one in a line to take plates of Ladoos from Ninja. Ninja picks the two plates in front, one from each row and gives that plate to people in which the number of ladoos is the smallest (if both plates contain equal numbers of ladoos then he serves any plate from the two plates) and places the other plate back to its position.

For Example : 
If ‘ROW1’ is [2, 5, 8, 17] and ‘ROW2’ is [1, 4, 8, 13, 20], then Ninja picks the first plates from each rows, plate containing 2 ladoos from ‘ROW1’ and a plate containing 1 ladoo from ‘ROW2’. 
Then he gives the plate with 1 Ladoo to the first person in line and places the other plate back to its position.

Can you tell how many ladoos the ‘K'th’ person will get?

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case contains three single space-separated integers ‘N’,  ‘M’ and ‘K’ where ‘N’ and ‘M’ denote the number of plates containing ladoos in ‘ROW1’ and ‘ROW2’  respectively and ‘K’ denotes the ‘K’th’ person in line waiting to be served.

The second line of each test case contains ‘N’ single space-separated integers, denoting the number of ladoos in each plate of the first row i.e. ‘ROW1’.

The third line of each test case contains ‘M’ single space-separated integers, denoting the number of ladoos in each plate of the second row i.e. ‘ROW2’.
Output Format : 
For each test case, print an integer denoting the number of ladoos the K'th person will get.

Print the output of each test case in a separate 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 <= N, M, K <= 10^5
K <= (N + M)
0 <= ROW1[i], ROW2[i] <= 10^5

where ROW1[i] and ROW2[i] denote the number of Ladoos in i’th plates of ROW1 and ROW2 respectively.

Time Limit: 1 second
Sample Input 1 :
2
5 4 3
3 11 23 45 52
4 12 14 18
1 1 2
1
2
Sample Output 1 :
11
 2
Explanation for Sample Output 1 :
For sample test case 1: 
1’st person will get 3 ladoos i.e a minimum of 3 and 4. Now  ‘ROW1’ :  [11, 23, 45, 52] and  ‘ROW2’ :  [4, 12, 14, 18].
2’nd person will get 4 ladoos i.e minimum of 11 and 4. Now  ‘ROW1’ :  [11, 23, 45, 52] and  ‘ROW2’ :  [12, 14, 18].
3’rd person will get 11 ladoos i.e minimum of 11 and 12. 

 For sample test case 2: 
1’st person will get 1 ladoos i.e a minimum of 1 and 2. Now  ‘ROW1’ :  [ ] and  ‘ROW2’ :  [2].
2’st person will get 2 ladoos because we have only one element left in ROW2 . Now  ‘ROW1’ :  [] and  ‘ROW2’ :  [].
Sample Input 2 :
2
5 3
1 3 6 7 10
3 5 5 7
3 3 2
10 20 20
1 2 3
Sample Output 2 :
3 
2
Explanation for Sample Output 2 :
For sample test case 1: 
1’st person will get 1 ladoo i.e minimum of 1 and 3. Now  ‘ROW1’ :  [3, 7, 10] and  ‘ROW2’ :  [3, 5, 5, 7].
2’nd person will get 3 ladoos i.e now from both rows we will get a plate of 3 ladoos so Ninja can give any one plate containing ladoos from each row. Let us assume Ninja give a plate from ‘ROW2’. Now  ‘ROW1’ :  [3, 7, 10] and  ‘ROW2’ :  [5, 5, 7].
3’rd person will get 3 ladoos i.e minimum of 3 and 5. Now  ‘ROW1’ :  [7, 10] and  ‘ROW2’ :  [5, 5, 7].

For sample test case 2: 
1’st person will get 1 ladoo i.e minimum of 10 and 1. Now  ‘ROW1’ :  [10, 20, 30] and  ‘ROW2’ :  [ 2, 3].
2’nd person will get 2 ladoos i.e  minimum of 10 and 2. Now  ‘ROW1’ :  [10, 20, 30] and  ‘ROW2’ :  [3].
Hint

What is the ‘K’th’ smallest element in union of two sorted arrays?.

Approaches (3)
Brute Force

First of all, let’s think about what we want to find. We are given two sorted arrays i.e. ‘ROW1’ and ‘ROW2’. In these two arrays, we want to find the number of  ladoos the ‘K'th’ person will get. More specifically, we want to find the ‘K’th’ smallest element in the combined and sorted array. The simplest way to find the ‘K’th’ smallest element is to first merge the two arrays and then directly retrieve the ‘K’th’ element.

 

Here is the algorithm :

  1. Declare a new array i.e. sortedRows of length M + N in which we can store all the elements of ‘ROW1’ and ‘ROW2’.
  2. Take three variables ‘a’, ‘b’ and ‘c’ which are used to indicate the position of the current element of ‘ROW1’, ‘ROW2’ and ‘sortedRows’ respectively.
  3. We run a loop while ‘a’ < ‘M’ and ‘b’ < ‘N’:
    • If  ROW1[a] <= ROW2[b]
      • sortedROw[c] = ROW1[a]
      • a++
    • Else
      • sortedRow[c] = ROW2[b]
      • b++
    • c++
  4. If there is any element left of the ‘ROW1’ then add the remaining elements of ‘ROW1’ i.e. run a loop while ‘a’ < ‘M’: 
    • sortedRow[c] = ROW1[a]
    • a++
    • c++
  5. If there is any element left of the ‘ROW2’ then add the remaining elements of ‘ROW2’ i.e. run a loop while ‘b’ < ‘N’: 
    • sortedRow[c] = ROW2[b]
    • b++
    • c++
  6. Return the ‘K’th’ element of the sortedRow.

       

 

Time Complexity

O(M+N)  where ‘M’ + ‘N’ is the combined length of ‘ROW1’ and ‘ROW2’ arrays/lists.

 

Because to find the resultant ‘sortedRow’ we traverse the whole ‘ROW1’ and  ‘ROW2’ arrays.

Space Complexity

O(M+N)  where ‘M’ + ‘N’ is the combined length of ‘ROW1’ and ‘ROW2’ arrays.

 

Because to find the resultant array we declare a new array i.e. ‘sortedRow’ of length ‘M’ + ‘N’.

Code Solution
(100% EXP penalty)
Kth Element of Two Sorted Arrays
Full screen
Console