Algorithm with O(m (log n + log m)) time complexity for finding kth smallest element in n*m matrix with each row sorted?

4
votes

I ran into an interview question recently.

We have m*n matrix such that each row is in non-decreasing order (sorted with distinct elements). design an algorithm on order O(m (log m+ log n)) to find k-th smallest element on this matrix (just one element as k-th smallest element).

I think this is not possible so search on Google and find this link and another solution and this answer to a similar question.

I think as follows:

  1. Put the median of all rows into an array and we find the median of this array in O(m) and called it pivot

  2. We find the rank of this element in O(m log n). i.e: in each row how many elements are lower than the pivot found in step (1).

  3. By comparing k and "rank of the pivot" we can know that in each row works on the right half or left half. (reduce to m*n/2 matrix.)

But the time complexity of this algorithm is O(m * log^2 n). What is the algorithm that can works on O(m (log n + log m))? Is there any idea?

1
javac++algorithmmathdata-structures
I think that the algorithm you suggested has a minor issue. The matrix will not reduce to m * n/2, but instead each row will be split roughly in half by the pivot. So after the first iteration rows will have different sizes in general case. - fdermishin
@fdermishin So you mean the proposed algorithm by me, is correct? is the time complexity correct? - Sammi524
Is the algorithm required to only use comparison operations? (for example, radix sort doesn't satisfy that condition) - user202729
The special case m==2 is possible. For m==3 it's very hard already. - user202729
@user202729 can we use a trick? we know for m sorted array with n element at whole, we know there is O(m log n) solution for finding k'th element, here we have m sorted array (m row) and m*n elements so we get O(m (logmn)) means O(m (log (m)+ log (n)) - Sammi524

1 Answers

0
votes

m - rows n - columns

  • Is it compulsory that you want a solution with O(m (log m+ log n)) Complexity?

  • I Can Think of a Solution with Complexity O(k * log-m) with extra space of O(m)

    • You can use a modified PriorityQueue (heap) DataStructure for this complexity
    class PQObject {
    int value; // PQ sorting happens on this int..
    int m; // And m and n are positions.
    int n;
}

  • You can just put all the values from the first column to the Priority Queue and Start popping until the kth smallest element

    • Every time you pop re-insert the next value of the row using m and n in the popped object.

  • Ultimately the problem comes down to find the kth smallest element in M sorted arrays.