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, 2k*log(k) = k*log(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