Kth Smallest Element in Sorted 2d-array
Given an n x n matrix, where every row and column is sorted in non-decreasing order. Find the kth smallest element in the given 2D array. For example, consider the following 2D array. The idea is to use min heap. Following are detailed step. 1) Build a min heap of elements from first row. A heap entry also stores row number and column number. 2) Do following k times. …a) Get minimum element (or root) from min heap. …b) Find row number and column number of the minimum element. …c) Replace root with the next element from same column and min-heapify the root. 3) Return the last extracted root. Algorithm :: #include<iostream> #include<climits> using namespace std; // A structure to store an entry of heap. The entry contains // a value from 2D array, row and column numbers of the value struct HeapNode { int val; // value to be stored int r; // Row number o...