# #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 :

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).

Get this bounty!!!

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