# Kth smallest element

Last updated: 17th Jan, 2021

#### Problem Statment

Given a N x N matrix, where every row and column is sorted in non-decreasing order. Find the kth smallest element in the matrix.
Example 1:
N = 4
mat[][] = {
{10, 20, 30, 40}
{15, 25, 35, 45}
{24, 29, 37, 48}
{32, 33, 39, 50}
}
K = 7
>>Output: 30
Explanation: 30 is the 7th smallest element.

Approach:

Min Heap stores the elements with minimum element at the top. Firstly add all elements and indexes of first column in heap/priority queue. Then add neighbour of topmost element and pop top of heap.Keep a count of popped elements. When count reaches k, then heap top will be kth smallest
Time and Space Complexity :
Time - O(N+log(k))
Space - O(N), where N is number of rows

###### C++ Code

    #define M 4
    #define N 4
    int kSmallest(int mat[M][N], int k){
    	//declare min heap with (int , (i,j)) structure
    	priority_queue<< pair >, vector > >, greater > > > min_heap;

    	//insert first column
    	for (int i = 0; i < M; ++i)
    	{
    		min_heap.push(make_pair(mat[i][0], make_pair(i,0)));

    	}
    	int count=7, ans;

    	// keep inserting next column element of current top and pop
    	while(count--){
    		int tempi=min_heap.top().second.first;
    		int tempj=min_heap.top().second.second;
    		ans=min_heap.top().first;
    		min_heap.pop();
    		min_heap.push(make_pair(mat[tempi][tempj+1], make_pair(tempi, tempj+1)));
    	}
    	return ans;
    }

    int main()
    {
       int mat[M][N] = { {10, 20, 30, 40},
                        {15, 25, 35, 45},
                        {24, 29, 37, 48},
                        {32, 33, 39, 50},
                    };
      	int k=7;
        cout<<kSmallest(mat, k);
        return 0;
    }