×

Search anything:

# K-th Smallest element in a row and column wise sorted matrix

#### Algorithms binary heap binary search Get this book -> Problems on Array: For Interviews and Competitive Programming

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.

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;
}

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;

priority_queue <struct element,vector <element>,compare > minheap;

for(int i=0;i<n;i++)
{
struct element current(matrix[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 and also answer <= mat[N-1][N-1]. So mat 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 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;

int low = matrix;
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 #### Shreya Shah

Intern at OpenGenus, B. Tech Student at Jabalpur Engineering College (JEC) in Information Technology, 2023.

K-th Smallest element in a row and column wise sorted matrix