Is there a way to find the kth smallest in 0(log n) time in 3 or more sorted arrays like we do in 2 and 1 sorted arrays
Asked
Active
Viewed 89 times
1
-
kth smallest from all the numbers in all the arrays? – SomeWittyUsername Dec 14 '15 at 23:29
-
You can't do it in O(log(n)) time because you need to look at every array so it has to be at least O(n) and according to http://cstheory.stackexchange.com/a/20955 there is an optimal solution. – Jerry Jeremiah Dec 14 '15 at 23:58
-
@SomeWittyUsername Yes. The whole diea is to do this like we do it when we try to find the kth smallest in 2 arrays. I just cant see how to modify that for 3 arrays – Lum Zhaveli Dec 15 '15 at 00:12