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.

Table of contents:

- Problem Statement
- Brute force approach
- Using min-heap data structure
- 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:

- Brute force approach
- Using min-heap data structure
- 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