2-D array's kth largest element



Given a N*N Matrix.
All rows are sorted, and all columns are sorted.
Find the Kth Largest element of the matrix.

Solution ::: All I could get is this

First of all, you only need to consider the left-top k*k matrix to find the k-th largest element. It’s guaranteed to be in that smaller matrix. This helps especially when k << n.

Then extract the first element of each row and put it in the max-heap with size K. Building the heap takes time k*log(k).

Then remove the max element from the heap and put the next element in the same row into the heap. This step takes k*log(k) time.

So in total, 2klog(k) = klog(k) time.
It only requires O(k) space.

There may be better selection algorithm with better best-case performance. If you know of a better algorithm than mine, let me know!

I am also having some problem in it’s implementation . Please someone help !!

How to solve this ?? Thanks in advance :slight_smile:


Your logic is absolutely correct. Incase you have any issues, look over to this link [at GeeksForGeeks][1]

Just instead of Min Heap(as in link, use MaxHeap(or Priority Queue).)

[1]: http://www.geeksforgeeks.org/kth-smallest-element-in-a-row-wise-and-column-wise-sorted-2d-array-set-1/


Okk bro thanks for the help :slight_smile: