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 