Kth smallest element in a row | kth largest element in a 2d array sorted row - wise and column - wise ; A structure to store entry of heap . The entry contains value from 2D array , row and column numbers of the value ; value to be stored ; Row number of value in 2D array ; Column number of value in 2D array ; A utility function to swap two HeapNode items . ; A utility function to minheapify the node harr [ i ] of a heap stored in harr [ ] ; This function returns kth smallest element in a 2D array mat [ ] [ ] ; k must be greater than 0 and smaller than n * n ; Create a min heap of elements from first row of 2D array ; Get current heap root ; Get next value from column of root 's value. If  the value stored at root was last value in its  column, then assign INFINITE as next value ; Update heap root with next value ; Heapify root ; Return the value at last extracted root ; driver program to test above function
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct HeapNode { int val ; int r ; int c ; } ; void swap ( HeapNode * x , HeapNode * y ) { HeapNode z = * x ; * x = * y ; * y = z ; } void minHeapify ( HeapNode harr [ ] , int i , int heap_size ) { int l = i * 2 + 1 ; int r = i * 2 + 2 ; if ( l < heap_size && r < heap_size && harr [ l ] . val < harr [ i ] . val && harr [ r ] . val < harr [ i ] . val ) { HeapNode temp = harr [ r ] ; harr [ r ] = harr [ i ] ; harr [ i ] = harr [ l ] ; harr [ l ] = temp ; minHeapify ( harr , l , heap_size ) ; minHeapify ( harr , r , heap_size ) ; } if ( l < heap_size && harr [ l ] . val < harr [ i ] . val ) { HeapNode temp = harr [ i ] ; harr [ i ] = harr [ l ] ; harr [ l ] = temp ; minHeapify ( harr , l , heap_size ) ; } } int kthSmallest ( int mat [ 4 ] [ 4 ] , int n , int k ) { if ( k < 0 && k >= n * n ) return INT_MAX ; HeapNode harr [ n ] ; for ( int i = 0 ; i < n ; i ++ ) harr [ i ] = { mat [ 0 ] [ i ] , 0 , i } ; HeapNode hr ; for ( int i = 0 ; i < k ; i ++ ) { hr = harr [ 0 ] ; int nextval = ( hr . r < ( n - 1 ) ) ? mat [ hr . r + 1 ] [ hr . c ] : INT_MAX ; harr [ 0 ] = { nextval , ( hr . r ) + 1 , hr . c } ; minHeapify ( harr , 0 , n ) ; } return hr . val ; } int main ( ) { int mat [ 4 ] [ 4 ] = { { 10 , 20 , 30 , 40 } , { 15 , 25 , 35 , 45 } , { 25 , 29 , 37 , 48 } , { 32 , 33 , 39 , 50 } , } ; cout << "7th ▁ smallest ▁ element ▁ is ▁ " << kthSmallest ( mat , 4 , 7 ) ; return 0 ; }