K th smallest element in row and coloumn wise sorted array

#1

give me the approach also provide code

#2

@ajayrajsingh_817

Approach: So the idea is to find the kth minimum element. Each row and each column is sorted. So it can be thought as C sorted lists and the lists have to be merged into a single list, the kth element of the list has to be found out. So the approach is similar, the only difference is when the kth element is found the loop ends.

Algorithm:

  1. The idea is to use min heap. Create a Min-Heap to store the elements
  2. Traverse the first row from start to end and build a min heap of elements from first row. A heap entry also stores row number and column number.
  3. Now Run a loop k times to extract min element from heap in each iteration
  4. Get minimum element (or root) from Min-Heap.
  5. Find row number and column number of the minimum element.
  6. Replace root with the next element from same column and min-heapify the root.
  7. Print the last extracted element, which is the kth minimum element.

Now Try making code on your own and if you get any errors let me know.

#3


gives wrong output

#4

@ajayrajsingh_817 you have to push next element from next row with same column like this:

pq.push(make_pair(v[x+1][y],make_pair(x+1,y)));