7
$\begingroup$

Given a matrix of size $n\times n$ with numbers, where every row is sorted, one can compute the $k$th smallest element in $O(n \log^2 n)$ time by simulating (implicitly) quick-select on this matrix (removing one log factor can be done by avoiding the binary search in each row). In fact, $O(n )$ time algorithm is possible if the columns are also sorted, see below for details by simulating some variant of QuickSelect on this matrix.

My question: Is there a reference that describes and analyzes how to simulate QuickSelect on an implicit set (like a row sorted matrix)?

This is not hard, but I would prefer not to write it down if somebody already did it. Thanks in advance...

More details

Fredrickson and Johnson showed how to get $O(n)$ time algorithm if both rows and columns are sorted http://epubs.siam.org/sicomp/resource/1/smjcat/v13/i1/p14_s1?isAuthorized=no. It is in fact not too hard to come up with an $O(n)$ randomized time algorithm by massively sampling in each iteration, estimating the interval where the element must lie, and then recursively continuing on the elements lying in this interval (this selection algorithm due to Rivest and Floyd is described in pages 47-51 in the randomized algorithms book by Motwani and Raghavan).

$\endgroup$

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.