In this article, we have discussed how can we find the kth smallest element in a given n x n matrix, in which every row and column is sorted in non-decreasing order.

Table of contents:

1. Problem Statement
2. Brute force approach
3. Using min-heap data structure
4. Using binary search

Problem statement

Problem statement: Find the kth smallest element in a given n x n matrix, in which every row and column is sorted in non-decreasing order.

Example:

• K=3, matrix:
  15, 25, 31, 43
  16, 27, 36, 45
  28, 30, 39, 49
  33, 35, 40, 50

Output: 25
Explanation: The 3rd smallest element = 25

• K=7, matrix:
  15, 18, 33
  17, 29, 37
  25, 31, 38

Output: 33
Explanation: The 7th smallest element is 33

We will solve this using three approaches:

1. Brute force approach
2. Using min-heap data structure
3. Using binary search

Brute force approach

In this approach we simply add all the elements of the matrix into an array, sort the array and return the k-th smallest number.

Algorithm:

• If given a matrix mat[][] of dimensions n x n, we create a linear array arr[] of size n*n.
• Now we add all the elements of mat into the arr.
• We then sort arr and return arr[k-1] (k-th largest element).

Implementation:

#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;

int kthSmallestElement(vector < vector<int> > matrix, int k)
{
    int n = matrix.size();
    
    if(k > n*n)
    {
        return -1;
    }

    if(k == 1)
    {   
        return matrix[0][0];
    } 

    vector <int> a;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            a.push_back(matrix[i][j]);
        }
    }
    
    sort(a.begin(),a.end());
    
    return a[k-1];
}
int main() 
{
    vector< vector<int> > matrix {
                              {15, 25, 31, 43},
                              {16, 27, 36, 45},
                              {28, 30, 39, 49},
                              {33, 35, 40, 50},
                              };
  
    int k = 3;
    int ans = kthSmallestElement(matrix,k);
  
    if(ans == -1){
        cout<<k<<" smallest element doesn't exist.";
    }
    else{
        cout<<k<<" smallest element is "<<ans<<endl;
    }
  
    return 0;
}

Complexity Analysis:

Time Complexity : T(n) = O(n^2 log(n^2))
Storing the matrix in an array requires O(n^2)time, Sorting the array requires O(n^2 log(n^2)), Taking the K th element takes O(1) time.
So the total time complexity is O(n^2 log(n^2)).

Space Complexity : O(n^2)
As we require an auxiliary of size n^2.

Using min-heap data structure

Here, the idea is to use min heap data structure to store the elements of the first row of the matrix, then one by one w pop elements from the heap and add the element from the matrix lying just below the last popped element. This is done until we obtain k-th smallest number.

Algorithm:

• Create a Min-Heap to store the elements such that, a heap entry also stores row number and column number.
• Traverse the first row and build a min heap of elements from first row.
• Run a loop k times to extract min element from heap and in each iteration do the following.
• Get minimum element that is the root from min heap.
• Find row number and column number of this element.
• Replace root with the next element from same column (element from the matrix lying just below the last popped element) and min-heapify the root.
• Lastly, print the kth minimum element, which is the last extracted element .

Implementation:

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

struct element
{
    int val;
    int i;
    int j;
    
    element(){}
    element(int element,int row,int col)
    {
        val = element;
        i = row;
        j = col;
    }
};

struct compare 
{ 
    bool operator()(element const& p1, element const& p2) 
    { 
        return p1.val > p2.val; 
    } 
}; 

int kthSmallestElement(vector < vector<int> > matrix,int k)
{
    int n = matrix.size();
    
    if(k > n*n)
    return -1;
    
    
    if(k == 1)
    return matrix[0][0];
    
    priority_queue <struct element,vector <element>,compare > minheap;
    
    for(int i=0;i<n;i++)
    {
        struct element current(matrix[0][i],0,i);
        minheap.push(current);
    }
    
    struct element kthsmall;
    
    for(int i=0;i<k;i++)
    {
        kthsmall = minheap.top();
        minheap.pop();
        
        if(kthsmall.i+1 >= n)
        {
            struct element current(INT_MAX,-1,-1);
            minheap.push(current);
        }
        
        else
        {
            struct element current(matrix[kthsmall.i + 1][kthsmall.j],kthsmall.i+1,kthsmall.j);
            minheap.push(current);
        }
    }
    
    return kthsmall.val;
    
}
int main() 
{
  vector< vector<int> > matrix {
                              {15, 25, 31, 43},
                              {16, 27, 36, 45},
                              {28, 30, 39, 49},
                              {33, 35, 40, 50},
                              };
  
    int k = 3;
    int ans = kthSmallestElement(matrix,k);
  
    if(ans == -1){
        cout<<k<<" smallest element doesn't exist.";
    }
    else{
        cout<<k<<" smallest element is "<<ans<<endl;
    }
  
    return 0;
}

Complexity Analysis:

Time Complexity: O(k logn)
Building a min-heap takes O(n) time and as heapify takes O(log n) time therefore k times heapify takes O(k logn) time.

Space Complexity: O(n),
Min-Heap stores one row at a time so the space complexity is O(n).

Using binary search

In this approach we use binary search to iterate over possible solutions. We know that answer >= mat[0][0] and also answer <= mat[N-1][N-1]. So mat[0][0] and mat[N-1][N-1] can represent the “range” i.e., the low and the high values for the Binary Search.

Algorithm:

• We start the Binary Search with low = mat[0][0] and high = mat[n-1][n-1].
• We then find mid of low and high. But this middle number is may not necessarily be an element in the matrix.
• We count all the numbers smaller than or equal to mid element in the matrix. We can do this in O(N) as the matrix is sorted.
• If this count is less than ‘K’, we update low = mid+1 and search in higher part of the matrix.
• Else if the count is greater than or equal to ‘K’, we update high = mid and search in the lower part of the matrix.
• When value of low and high become equal and the loop terminates, low contains the value of k-th smallest element.

Example:
matrix =
15, 25, 31, 43
16, 27, 36, 45
28, 30, 39, 49
33, 35, 40, 50

low=15 and high=50

Steps:
low high mid count
15    50    32    7    (count is not lesser than 3 ∴ high = mid)
15    32    23    2    (count is lesser than 3 ∴ low = mid + 1)
24    32    28    5    (count is not lesser than 3 ∴ high = mid)
24    28    26    3    (count is not lesser than 3 ∴ high = mid)
24    26    25    3    (count is not lesser than 3 ∴ high = mid)
24    25    24    2    (count is lesser than 3 ∴ low = mid + 1)
25    25                 (low is not lesser than mid, loop terminates)

Implementation:

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int kthSmallestElement(vector < vector<int> > matrix,int k)
{
    int n = matrix.size();
        
    if(k == 0 || k > n*n || n == 0)
    return -1;
    
    if(k == 1)
    return matrix[0][0];
    
    int low = matrix[0][0];
    int high = matrix[n-1][n-1];
    
    while (low < high) 
    {
        int mid = low + (high - low) / 2;
        int count = 0;
        int j = n - 1;
    
        for (int i = 0; i < n; i++) 
        {
            while (j >= 0 && matrix[i][j] > mid) 
                j--;
                
            count += (j + 1);
        }
        
        if (count < k) 
            low = mid + 1;
        
        else 
            high = mid;
    } 
    
    return low;
}
int main() 
{
  vector< vector<int> > matrix {
                              {15, 25, 31, 43},
                              {16, 27, 36, 45},
                              {28, 30, 39, 49},
                              {33, 35, 40, 50},
                              };
  
    int k = 3;
    int ans = kthSmallestElement(matrix,k);
  
    if(ans == -1){
        cout<<k<<" smallest element doesn't exist.";
    }
    else{
        cout<<k<<" smallest element is "<<ans<<endl;
    }
  
    return 0;
}

Complexity Analysis

Time Complexity : O(n)
O(n log(max-min)) = O(n log(const)) = O(n)
max and min both are integers as max-min is the difference between largest and smallest values in the matrix so the maximum difference can’t be more than maximum integer value and hence the difference max-min becomes constant.

Space Complexity : O(1)

So by the end of this article you must have a clear understanding of how to find the kth smallest element in a row and column wise sorted matrix.

With this article, you must have a strong knowledge to find the