5

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?

Sammi524
  • 61
  • 3
  • 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 Jan 16 '21 at 11:38
  • @fdermishin So you mean the proposed algorithm by me, is correct? is the time complexity correct? – Sammi524 Jan 16 '21 at 13:19
  • Is the algorithm required to only use comparison operations? (for example, radix sort doesn't satisfy that condition) – user202729 Jan 16 '21 at 15:28
  • The special case m==2 is possible. For m==3 it's very hard already. – user202729 Jan 16 '21 at 15:34
  • @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 Jan 16 '21 at 16:01
  • @user202729 would you please present it here to discuss with others. please add as simple as possible step (not advanced) – Sammi524 Jan 16 '21 at 16:04
  • Thinking about it again, it's actually m * (log m + log n) (which satisfies the condition of the question) – user202729 Jan 16 '21 at 16:29
  • @user202729 would you please read the attached links too and also please see problem 4 here https://courses.engr.illinois.edu/cs374/sp2017/labs/solutions/lab6-sol.pdf – Sammi524 Jan 16 '21 at 16:41
  • Wait... this question asks exactly the same thing as the linked question, and the linked answer claims that it works in the required complexity. – user202729 Jan 16 '21 at 16:43
  • @user202729 very hard and also nice question. I see all linked post, nothing... –  Jan 16 '21 at 23:14
  • @DaviedZuhraph ...? That [linked post](https://stackoverflow.com/questions/64916213/fastest-algorithm-for-kth-smallest-element-or-median-finding-on-2-dimensional/65043109#65043109) (to another answer on SO) have an answer. – user202729 Jan 17 '21 at 04:33
  • @user202729 it's strange... –  Jan 17 '21 at 11:56
  • @DaviedZuhraph What is strange? Are you saying that you don't understand the linked answer? Or what? – user202729 Jan 22 '21 at 08:15

2 Answers2

0

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.

Swargam
  • 1
  • 1
  • !! just rows is sorted here not columns and rows –  Jan 21 '21 at 15:04
  • Yes, Just rows are sorted. So I created a PQ for the values of the first column. And will keep track of which row each element belongs to. I will pop from PQ which will return me the first smallest Element. Then will insert into the PQ the next row element for the poped and will pop again. That's why the problem is simply put -> To find the kth smallest element in M sorted arrays. – Swargam Jan 22 '21 at 07:31
0

A recent paper by Kaplan et al gives the optimal algorithms for this problem, at least from a big-O perspective. Specifically, by using the soft heap data structure, they give algorithms that run in time

  • O(m + k) for the case where k ≤ 2m;
  • O(m log (k/m)) for the case where k ≥ 2m; and
  • O(m + Σ log(ni + 1)) in general, where ni is the number of items in row i less than or equal to the kth-smallest item.

All of these runtimes are optimal in that, assuming we can only use comparison-based algorithms, none of the runtimes can be improved in a big-O sense.

The algorithms involved here are nontrivial but are much simpler than previous algorithms meeting similar time bounds. The use of the soft heap data structure is the key to making everything work correctly and quickly.

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065