#StackBounty: #algorithms #time-complexity #data-structures #sorting #arrays Find $k$'th smallest element in matrix with sorted rows

Bounty: 100

This is very hard question as mentioned on some site on google and firstly introduce on Interview Amazon Question.

We have an $mtimes n$ matrix in which all rows are sorted in ascending order and all elements are distinct. We want to find the $k$-th smallest element in this matrix.

There is an $O(m (log m + log n))$ algorithm for doing this!

I see lots of posts, especially here, but as Yuval Filmus mentioned in comments there are difference in large value of $k$.

We are familiar with median of medians method that throw half of elements with median, but here there is a very challenging question. How is this time complexity reached?

Update: this is exactly copy of one Ex. in Jeff Algorithms Book (Book Page 55 Ex: 21 Part C, Chapter Recursion :

enter image description here

As Yuval tell in comments, the previous question algorithms not complete so this is a good question for a complete algorithm in given time complexity.

Update 2: this is local multiple choice interview questions that we should choose the best option as the time complexity that I mentioned in my question (options listed here).

enter image description here


Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.