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

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

Okk bro thanks for the help :slight_smile: