I was trying to do kth element in 2 sorted arrays but I couldn’t really understood the divide and conquer approach from gfg. They have missed some comparison signs and forgot to correct them.
Can someone help me understanding this using divide and conquer approach?
Hi, sorry I haven’t been really active lately, so couldn’t reply sooner
I believe the problem just requires us to merge the two lists, and then sort them. Then we print the k-1 th element of the list
Yes. I tried my approach and got Correct Answer
#Python code
for _ in range(int(input())):
N,m,k = map(int, input().split())
arr1 = list(map(int, input().split()))
arr2 = list(map(int, input().split()))
arr1.extend(arr2)
arr1.sort()
print(arr1[k - 1]) #note, no. of lines can be reduces, but I have kept it this way to show each step clearly
I got this. But I asked for divide and conquer approach. The time complexity of your code is
O((N+M)log(N+M)), you can do this in O(K) using 2-pointers which is better than previous approach but I asked for divide and conquer approach that has complexity of O(log(N)+log(M)).
PS: Even the divide and conquer has another efficient implementation that will have time complexity of O(log(K)
@pakalupapito Hey Pal!!!
The code is actually quite simple but there are next to no comments that’s why you must have not understood but that’s the reason we are here 
The answer is a little long but if you read completely, you will understand as I wrote the answer for an absolute beginner to understand and you are 3 star so you will surely get it.
instead of using inbuilt functions, the guy sorted himself but really the code works longer than required. We need the Kth element so we need the list till Kth element only. No real need to get the whole list!!!
we know the two given arrays are sorted so we don’ really to sort them again and we are sure that the element arr1[x]<arr1[y] where x<y.
now we can take d till k instead of m+n because we don’t really need to find full list(because we need to find only one index. If question asked more than 1 index then finding full list will be helpful). Instead of making a list, we will make a integer variable(answer) which stores the last no. of list at that moment.
now in the first while loop we take 3 conditions instead of 2 that i<m, j<n and d<k. now what this loop does is compare elements arr1[i] and arr2[j]. if arr1[j] is smaller than then the answer to arr1[i] and increase i by 1 else arr2[j] and increase j by 1. off course we increase d also by 1.
now if the loop break then it can mean 3 things:
first: value of i reached m. This means first array is completed now and we have to take only arr2 till d=k-1 so we run a while loop which has condition while j<n and d<k and make the answer=arr2[j], increase j and d by 1. if this loop breaks then it means we got answer. We will have this loop no matter what because it won’t run if the first loop broke because of d reaching k. Same will apply to the next loop.
second: value of j reached n. This means second array is completed now and we have to take only arr1 till d=k-1 so we run a while loop which has condition while i<m and d<k and make the answer=arr1[i], increase i and d by 1. if this loop breaks then it means we got answer.
third: value of d reached k. This applies even if loop 2 or 3 ran and broke. This is the end. Hooray!! we got the Kth element of merged the sorted list. print the answer.
Hope you understood now.
You’re welcome 