Find K-th Element

Easy
0/40
Average time to solve is 10m
profile
Contributed by
13 upvotes
Asked in companies
IBMSamsung

Problem statement

Ninja has been given two sorted arrays/lists, ‘ARR1’ and ‘ARR2’ of lengths ‘M’ and ‘N’ respectively. He is also provided with an integer ‘K’. He has to find the ‘K’th element (1 based indexing) in the sorted array/list of length ‘M + N’ made by merging ‘ARR1’ and ‘ARR2’.

For example :

‘ARR1’ = {1, 4, 6, 7} 
‘ARR2’ = {2, 3, 5, 6} 
‘K’ = 6

So the sorted array after merging ‘ARR1’ and ‘ARR2’ will be:
{1, 2, 3, 4, 5, 6, 6, 7}
So the 6th element (1 based indexing) is in the new sorted merged array/list is 6.

As Ninja is busy with the preparation of his upcoming exams so, he asks you for help. Can you help Ninja to solve this problem?

Follow Up :

Try to do this problem without using any extra space.
Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains a single integer T’, representing the number of test cases.
Then the ‘T’ test cases follow.

The first line of each test case contains three single space-separated numbers, ‘M’, ‘N’ and ‘K’, denoting the size of ‘ARR1’, the size of ‘ARR2’, and the position of the element in the new sorted array/list.

The second line contains ‘M’ space-separated distinct integers denoting the ‘ARR1’ elements.

The third line contains ‘N’ space-separated distinct integers denoting the ‘ARR2’ elements.

Output format:

For each test case print a single integer representing the ‘K’th element in the new sorted array.

The output of every test case will be printed in a separate line.

Note :

You don’t have to print anything, it has already been taken care of. Just implement the given function.

Constraints

1 <= T <=100
1 <= M,N <= 10^4
1 <= K <= M+N
0 <=  ARR1[i]’ , ARR2[i] <= 10^5

Where 'ARR1[i]' and 'ARR2[i]' denote the i'th element of 'ARR1' and 'ARR2' respectively.

Time limit: 1 sec

Sample input 1:

2
4 3 4
1 4 7 10
2 5 6
1 1 2
7
1

Sample output 1:

5
7

Explanation for sample input 1:

For test case 1:
The sorted array/list made by merging ‘ARR1’ and ‘ARR2’ = {1, 2, 4, 5, 6, 7, 10}.
 We can see the element at the 4th position is 5.

For test case 2:
The sorted arraylist made by merging ‘ARR1’ and ‘ARR2’ = {1, 7}.
We can see the element at the 2nd position is 7.

Sample input 2:

2
5 5 6
1 2 3 4 5
7 8 9 10 11
2 3 1
5 6
1 4 8

Sample output 2:

7
1

Explanation for sample input 2:

For test case 1:
The sorted array made by merging ‘ARR1’ and ‘ARR2’ = {1, 2,3 ,4, 5, 7, 8, 9, 10, 11}.
We can see the element at the 6th position is 7.

For test case 2:
The sorted array made by merging ‘ARR1’ and ‘ARR2’ = {1, 4, 5, 6, 8}.
We can see the element at the 1st position is 1.
Hint

Can you think of a brute force approach?

Approaches (3)
Brute Force

The idea is very simple. We will make a new array/list say ‘ARR3’ by appending ‘ARR1’ at end of ‘ARR2’ or by appending ‘ARR2’ at the end of ‘ARR1’. We will sort ‘ARR3’ and can easily return the ‘K’th element.

 

Complete Algorithm:

 

  1. Let’s make an integer array/list ‘ARR3’ of length ‘M+N’.
  2. Iterate over ‘ARR1’ for 0 <= i <= ‘M’ and do:
    1. ‘ARR3[i]’ = ‘ARR1[i]’
  3. Iterate over ‘ARR2’ for 0 <= i <= ‘N’ and do:
    1. ‘ARR3[i+M]’ = ‘ARR2[i]’
  4. Sort the array ‘ARR3’.
  5. Return ‘ARR3[K - 1]’.
Time Complexity

O((M + N) * log(M + N)), where ‘M’ is the size of the array/list ‘ARR1’ and ‘N’ is the size of ‘ARR2’.

 

As we are sorting an array of length ‘M + N’. 

Space Complexity

O(M + N), where ‘M’ is the size of the array/list ‘ARR1’ and ‘N’ is the size of ‘ARR2’.

 

As we are using an extra array/list of length ‘M + N’.

Code Solution
(100% EXP penalty)
Find K-th Element
Full screen
Console