Find the 'K'th Largest Element in 'N' Sorted Arrays

This is an algorithm for Order Statistics in Sorted Arrays.
Main Algorithm: 3:20

Prerequisites:

Relevant Links:

[umangmalhotra]

Title of the video - Find the 'K'th Largest Element in 'N' Sorted Arrays
Title written on the board - Nth largest in K sorted Arrays
😕

[yosihashamen]

Finally a good explanation for this question.

[surajagarwal]

i used it and got AC but i have a doubt... how the complexity is better than the previous one?

and thank u for this....this helps me a lot !!

[cureyou]

In your approach, if I have one array as [1, 6, 7], the other as [2, 8], and I want to find the 5th largest element.

First I choose 6 from array 1 and find the insertion place as index 1. Then do binary search on the second array and find the insertion place as index 1(where number 8 lies in). Since 1+1<5, I will then slice off the left subarrays in two arrays and only look at the right subarrays. So the array becomes [7] and [], which is clearly wrong.

If I include the "index" element and get [6, 7] and [8], k=k-L=5-2=3. So I look for the third largest element in these two arrays, and repeating the same steps as above I get index 0 and 0, so I need to cut off the left subarrays again. However, at this time, if I cut off 6 and 8, the answer will be wrong, and if I leave 6 and 8 as it is, I will encounter infinite loop.

Therefore, I think there is something with your approach. Do you think my analysis is right?

[nitishkumar-pyru]

I think we can do it better. We can do a binary search on our answer. Our answer will be in the search space [min_element, max_element]. And we have a function say f(x) that tells the number of elements less than x among all N arrays in n*log(avg_len_of_arrays) - simply doing a binary search on all n sorted arrays. So, using the above information and the fact that the above-said function f(x) is a monotonic increasing function for x - we can land on the kth smallest element using the concept of binary search. The time complexity will be O( n* log(range) * log(avg_length_of_array)). For larger n this will be optimal. What do you say?

[anktrj]

There was a doubt . . . We can use the fact that arrays are sorted then we can call merge function of merge sort and make a new sorted array in N*L*logN where L is length of the arrays. Then we can check the kth idex for the answer. This take N*L extra space. Please Correct me if I am wrong.

[neilnatarajan]

Does your time complexity analysis take into account the overhead of finding the longest list each iteration? That would seem to be similar to the cost of finding the min of N elements each iteration or using a priority queue (insertion time). I am then confused as to the comparison between the two.

[gouthamreddy]

Nicely explained . Does this work if dublicates elements exists in the arrays . Just confused, in that case is it a kth non distinct element ?

[vartikasharma]

what if we add these arrays in Set( for distinct elements) sort them using stream and print the index required? isn't that a better approach?

[cristianouzumaki]

The question is basically Nth largest element in k*k matrix if all arrays are of same k length

[AmitKumar-sjgr]

I don't think its practically better than heap approach. Min Heap is much better complexity, as arrays are already sorted, so in best case if you have already put the correct last k elements from greatest array, other arrays, reverse insertion in heap will be blocked with first(last index) element itself.

[RS-]

brilliant video. has anyone implemented it flawlessly (the 0 index handling of arrays is a pain!!
)

[jamesqiu]

simple and clear presentation!!! hands down!

[HimanshuPunetha]

you mentioned that complexity is N^2 (log E)^2, so how is it better than the algorithms you mentioned before . Like for heap algo the complexity you mentioned was NlogK +K

[SmartProgramming]

really awesome, the way you have explained is really great, thanks a lot brother 👍👍🙂🙂

[navinsingh]

If L represents how many numbers are less than the chosen number, say x (from the greatest length array) and G is how many numbers that are greater than x, shouldn't the comparison of K be done with G instead of L since we are focusing on Kth "largest" number?

[shivamkhatri]

At 09:18 K shouldn't be changed?
rather the low of the L3 array should be updated to its middle + 1 ?

[ravikumar-yqdf]

change the title of video . n and k are conflicting with video and title

[niazmdkhan]

If u randomize the pvot i think yhe time complexity will be reduced by n times.

[techdiscussion]

we can use heap to find the third largest..