Last Updated: 3 Mar, 2021

Find K-th Element

Easy

Asked in companies

Solve now

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.

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

Solve now

Approaches

01 Approach

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:

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

Solve now

02 Approach

In the earlier approach, we used an extra array/list ‘ARR3’ to store the elements of both arrays/lists, but we did not make any use of the fact that both arrays are sorted. This time we will traverse both the arrays/lists simultaneously and alternatively. We will traverse the arrays/lists in such a way that it can give us the final sorted array/list.

Complete Algorithm:

Initialize an integer variable ‘INDEX1’ = 0, which will be used to iterate over ‘ARR1’.
Initialize an integer variable ‘INDEX2’ = 0, which will be used to iterate over ‘ARR2’.
Initialize an integer variable ‘COUNT’ = 0, this will count the total number of elements we have iterated so far in ‘ARR1’ and ‘ARR2’.
Run a loop while ‘INDEX1’< ‘M’ and ‘INDEX2’ < ‘N’ and do:
- If ‘ARR1 [INDEX1] ’ is less than ‘ARR2 [INDEX2] ’ :
  - If ‘COUNT’ is equal to ‘K’ - 1 :
    - Return ‘ARR1 [ INDEX1] ’
  - Increase ‘INDEX1’ by 1.
  - Increase ‘COUNT’ by 1.
- Otherwise do:
  - If ‘COUNT’ is equal to ‘K’ - 1 :
    - Return ‘ARR2 [ INDEX2]’.
  - Increase ‘INDEX2’ by 1.
  - Increase ‘COUNT’ by 1.
Run a loop while ‘INDEX1’ < ‘M’ and do:
- If ‘COUNT’ is equal to ‘K’ - 1 :
  - Return ‘ARR1 [ INDEX1]’.
- Increase ‘INDEX1’ by 1.
- Increase ‘COUNT’ by 1.
Run a loop while ‘INDEX2’ < ‘N’ and do:
- If ‘COUNT’ is equal to ‘K’ - 1 :
- Return ‘ARR2 [ INDEX2]’.
- Increase ‘INDEX2’ by 1.
- Increase ‘COUNT’ by 1.

Solve now

03 Approach

The idea is to use the divide and conquer technique and decrease the time complexity. So we will recursively call the given function and each time we will reject one half from any one of two arrays according to the circumstances.

Complete Algorithm:

Base Case :

If the length of one array/list is equal to zero return ‘K’th element of another array/list.

Recursive calls:

If positions of mid of ‘ARR1’ + mid of ‘ARR2’ is less than ‘K’:
- If the element at mid of ‘ARR1’ is greater than the element at mid of ‘ARR2’:
  - We can safely reject the first half of ‘ARR2’.
  - Adjust the value of ‘K’ as:
    - ‘K’ = ‘K’ - mid of ‘ARR2’ - 1.
- Otherwise:
  - We can safely reject the first half of ‘ARR1’.
  - Adjust the value of ‘K’ as:
    - ‘K’ = ‘K’ - mid of ‘ARR1’ - 1.
If mid of ‘ARR1’ + mid of ‘ARR2’ is greater than ‘K’:
- If the element at mid of ‘ARR1’ is greater than the element at mid of ‘ARR2’:
  - We can safely reject the second half of ‘ARR1’.
- Otherwise:
  - We can safely reject the second half of ‘ARR2’.

Solve now