# Find $k$'th smallest element in matrix with sorted rows

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

We have an $$m\times 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).

• It's exactly the same question as the other one. – Yuval Filmus Nov 18 at 12:11
• Earlier you were aiming at a time complexity of $O(k\log(mn))$, yet here you write $O(m\log(mn))$. Which is it? – Yuval Filmus Nov 18 at 12:11
• A complexity of $O(m+k \log(mn))$ is easy to obtain. In fact $O(m+k \log m)$ suffices: keep a min-heap $H$. Initially $H$ contains the elements from the first column of the matrix. Then iteratively extract one element $x$ from $H$, return $x$ as the next smallest element, and if $x$ had coordinates $(i,j)$ in the matrix, push the element at coordinates $(i, j+1)$ in $H$ (if any). It is easy to see that this algorithm returns the elements of the matrix in sorted order and that each iteration requires $O(\log m)$ time. It then suffices to only execute the first $k$ iterations. – Steven Nov 18 at 12:16
• For $k = \Omega(\frac{m}{\log m})$ this is a $O(k \log m)$-time algorithm. For $k = o(\frac{m}{\log m}$) we still have a lower bound of $\Omega(m)$ since at least one element from each row needs to be accessed at least once by any correct algorithm (even for $k=1$). – Steven Nov 18 at 12:22
• I don’t work for you. – Yuval Filmus Nov 20 at 9:56