0
$\begingroup$

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 :

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

$\endgroup$
  • 1
    $\begingroup$ It's exactly the same question as the other one. $\endgroup$ – Yuval Filmus Nov 18 at 12:11
  • 3
    $\begingroup$ Earlier you were aiming at a time complexity of $O(k\log(mn))$, yet here you write $O(m\log(mn))$. Which is it? $\endgroup$ – Yuval Filmus Nov 18 at 12:11
  • 1
    $\begingroup$ 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. $\endgroup$ – Steven Nov 18 at 12:16
  • $\begingroup$ 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$). $\endgroup$ – Steven Nov 18 at 12:22
  • 2
    $\begingroup$ I don’t work for you. $\endgroup$ – Yuval Filmus Nov 20 at 9:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.