# K-th Smallest Element in a Sorted Matrix

Difficulty Level Medium
Array Binary Search Heap MatrixViews 3285

In K-th Smallest Element in a Sorted Matrix problem, we have 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.

## Example

```Input 1:
k = 3 and
matrix =
11, 21, 31, 41
16, 26, 36, 46
25, 30, 38, 49
33, 34, 40, 50
Ouput: 21
Explanation: The 3rd smallest element = 21

Input 2:
k = 7 and
matrix =
12, 23, 31
17, 27, 36
24, 29, 38
Ouput: 31
Explanation: The 7th smallest element is 30
```

## Types of Solution for K-th Smallest Element in a Sorted Matrix

1. Naive/Brute Force
2. using min Heap data structure
3. Binary Search

### Naive/Brute Force

#### Approach

This approach involves simply adding all the elements of the matrix into an array, sorting the array and returning the k-th smallest number.

#### Algorithm for K-th Smallest Element in a Sorted Matrix

1. given a matrix mat[][] of dimensions n x n, create a linear array arr[] of size n*n.
2. Add all the elements of mat into the arr.
3. Sort arr and return arr[k-1] (k-th largest element).

#### Implementation for K-th Smallest Element in a Sorted Matrix

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

// function to find k-th largest element
int kthSmallest(vector < vector<int> > mat,int k)
{
int n = mat.size();

if(k > n*n)
return -1;

// smallest element is the first element of the matrix
if(k == 1)
return mat;

// define array and push contents of the matrix into it
vector <int> arr;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
arr.push_back(mat[i][j]);

// sort the array and obtain k-th smallest element
sort(arr.begin(),arr.end());

return arr[k-1];
}

int main()
{
vector< vector<int> > mat {
{11, 21, 31, 41},
{16, 26, 36, 46},
{25, 30, 38, 49},
{33, 34, 40, 50}
};

int k = 3;
int kthsmall = kthSmallest(mat,k);

if(kthsmall == -1)
cout<<"3rd smallest element doesn't exist.";
else
cout<<"3rd smallest element = "<<kthsmall<<endl;

return 0;
}```
`3rd smallest element = 21`
##### Java Program
```import java.io.*;
import java.util.*;

class tutorialCup
{
// function to find k-th largest element
static int kthSmallest(ArrayList<ArrayList<Integer>> mat,int k)
{
int n = mat.size();

if(k > n*n)
return -1;

// smallest element is the first element of the matrix
if(k == 1)
return mat.get(0).get(0);

// define array and push contents of the matrix into it
ArrayList <Integer> arr = new ArrayList <Integer>();
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)

// sort the array and obtain k-th smallest element
Collections.sort(arr);

return arr.get(k-1);
}

public static void main (String[] args)
{
ArrayList<ArrayList<Integer>> mat = new ArrayList<ArrayList<Integer>>();

int k = 3;
int kthsmall = kthSmallest(mat,k);

if(kthsmall == -1)
System.out.println("3rd smallest element doesn't exist.");
else
System.out.println("3rd smallest element = "+kthsmall);

}
}```
`3rd smallest element = 21`

#### Complexity Analysis

1. Time Complexity : T(n) = O(n2)
2. Space Complexity : A(n) = O(n2)

### Using min Heap data structure

#### Approach

we use heap data structure(priority queue/min heap) to store the elements of the first row of the matrix, then one by one pop elements from the heap and add the element from the matrix lying just below the last popped element. This is done until k-steps obtain k-th largest number. The algorithm is discussed below :

#### Algorithm for K-th Smallest Element in a Sorted Matrix

1. deal with the base cases explicitly(n = 0,1).
2. define a min-heap pq.
3. add the elements from the first row of mat[][] (input matrix) into pq.
4. Now, run a loop k-times.  the loop variable is i, inside that loop perform steps below :
• pop an element from pq and store the popped element into kthsmall.
• add the element lying in mat[][] just below kthsmall into pq.
5. After the loop ends, return the last element value stored in kthsmall (ie kthsmall.num).  #### Implementation for K-th Smallest Element in a Sorted Matrix

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

// define a strucure
// to store a particular value from the matrix
// it's row and column number
struct element
{
int num;
int i;
int j;

// define constructors
element(){}
element(int element,int rownum,int colnum)
{
num = element;
i = rownum;
j = colnum;
}
};

// this is an strucure which implements the
// this will help us in creating a heap for storing
// values of element(struct) data type
struct compare
{
bool operator()(element const& p1, element const& p2)
{
return p1.num > p2.num;
}
};

// function to find k-th largest element
int kthSmallest(vector < vector<int> > mat,int k)
{
int n = mat.size();

if(k > n*n)
return -1;

// smallest element is the first element of the matrix
if(k == 1)
return mat;

// define a min Heap
priority_queue <struct element,vector <element>,compare > pq;

// push all the elements of first row
// along with their row and column numbers
// into a min heap
for(int i=0;i<n;i++)
{
struct element curr(mat[i],0,i);
pq.push(curr);
}

// define a variable to process each value stored in min heap
struct element kthsmall;

// pop from heap for k steps
for(int i=0;i<k;i++)
{
kthsmall = pq.top();
pq.pop();

// if last popped element lies in the last row\
// dont need to push any number
if(kthsmall.i+1 >= n)
{
struct element curr(INT_MAX,-1,-1);
pq.push(curr);
}
/* push the element below (element in the same column as the element itself)
the last element popped from the minheap*/
else
{
struct element curr(mat[kthsmall.i + 1][kthsmall.j],kthsmall.i+1,kthsmall.j);
pq.push(curr);
}
}

// return the element last popped from the heap pq
return kthsmall.num;

}

int main()
{
vector< vector<int> > mat {
{11, 21, 31, 41},
{16, 26, 36, 46},
{25, 30, 38, 49},
{33, 34, 40, 50}
};

int k = 3;
int kthsmall = kthSmallest(mat,k);

if(kthsmall == -1)
cout<<"3rd smallest element doesn't exist.";
else
cout<<"3rd smallest element = "<<kthsmall<<endl;

return 0;
}```
`3rd smallest element = 21`
##### Java Program
```import java.io.*;
import java.util.*;

/*
define a strucure
to store a particular value from the matrix
it's row and column number
*/
public class element
{
public int num;
public int i;
public int j;

public element(){}

public element(int element,int rownum,int colnum)
{
num = element;
i = rownum;
j = colnum;
}

public int numReturn()
{
return num;
}
}

class tutorialCup
{
// function to find k-th largest element
static int kthSmallest(ArrayList<ArrayList<Integer>> mat,int k)
{
int n = mat.size();

if(k > n*n)
return -1;

// smallest element is the first element of the matrix
if(k == 1)
return mat.get(0).get(0);

// Comparator forms heap using num attribute of object of element type
// sorts the heap using obj.num value
// where obj is an object of element type
Comparator<element> sorter = Comparator.comparing(element::numReturn);
// define a min Heap
PriorityQueue <element> pq = new PriorityQueue<element>(sorter);

// push all the elements of first row
// along with their row and column numbers
// into a min heap
for(int i=0;i<n;i++)
{
element curr = new element(mat.get(0).get(i),0,i);
}

// define a variable to process each value stored in min heap
element kthsmall = new element();

// pop from heap for k steps
for(int i=0;i<k;i++)
{
kthsmall = pq.peek();
pq.poll();

// if last popped element lies in the last row\
// dont need to push any number
if(kthsmall.i+1 >= n)
{
element curr = new element(Integer.MAX_VALUE,-1,-1);
}
/* push the element below (element in the same column as the element itself)
the last element popped from the minheap*/
else
{
element curr = new element(mat.get(kthsmall.i + 1).get(kthsmall.j),kthsmall.i+1,kthsmall.j);
}
}

// return the element last popped from the heap pq
return kthsmall.num;
}

public static void main (String[] args)
{
ArrayList<ArrayList<Integer>> mat = new ArrayList<ArrayList<Integer>>();

int k = 3;
int kthsmall = kthSmallest(mat,k);

if(kthsmall == -1)
System.out.println("3rd smallest element doesn't exist.");
else
System.out.println("3rd smallest element = "+kthsmall);

}
}```
`3rd smallest element = 21`

#### Complexity Analysis

1. Time Complexity : T(n) = O(n + klogn)
2. Space Complexity : A(n) = O(n)

### Binary Search

#### Approach

We can Apply Binary Search on the matrix mat[][], however, this is different from a conventional binary search as in this case we consider “number range”(matrix values itself) instead of the “index range”. As we know that the smallest number of our matrix is at the top left corner and the biggest number is at the bottom lower corner. These two numbers can represent the “range” i.e., the lo and the hi values for the Binary Search. below we explain how we implement our algorithm.

#### Algorithm for K-th Smallest Element in a Sorted Matrix

1. Start the Binary Search with `lo = mat` and `hi = mat[n-1][n-1]`.
2. Find `mid` of the `lo` and the `hi`. This `middle` number is NOT necessarily an element in the matrix.
3. Count all the numbers smaller than or equal to `mid` in the matrix. As the matrix is sorted, we can do this in O(N).
4. If the count is less than ‘K’, we can update `lo = mid+1` to search in the higher part of the matrix
5. Else if the count is greater than or equal to ‘K’, we can update `hi = mid` to search in the lower part of the matrix in the next iteration.
6. At some point lo and hi become equal in values and the loop terminates. lo contains the value of k-th smallest element as we iteratively narrowed down our search range to a single matrix element.

#### Implementation for K-th Smallest Element in a Sorted Matrix

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

// function to find k-th largest element
int kthSmallest(vector < vector<int> > mat,int k)
{
int n = mat.size();

if(k == 0 || k > n*n || n == 0)
return -1;

if(k == 1)
return mat;

// define smallest and largest element in the matrix as
// lower range &
// upper range
int lo = mat;
int hi = mat[n-1][n-1];

// perform binary search (by value)
// between smallest(top-left) and largest(bottom-down) values
while (lo < hi)
{
int mid = lo + (hi - lo) / 2;
int count = 0;
int j = n - 1;

// find out how many numbers are greater than mid
// between lo and hi
for (int i = 0; i < n; i++)
{
while (j >= 0 && mat[i][j] > mid)
j--;

count += (j + 1);
}

// if number of such element is less than k
// narrow the search range by increasing lo value
if (count < k)
lo = mid + 1;
// if number of such element is greater or equal to k
// narrow the search range by decreasing hi value
else
hi = mid;
}

// after iteratively narrowing the search range
// you narrow down to a single element in the matrix
// which is k-th smallest element
return lo;
}

int main()
{
vector< vector<int> > mat {
{11, 21, 31, 41},
{16, 26, 36, 46},
{25, 30, 38, 49},
{33, 34, 40, 50}
};

int k = 3;
int kthsmall = kthSmallest(mat,k);

if(kthsmall == -1)
cout<<"3rd smallest element doesn't exist.";
else
cout<<"3rd smallest element = "<<kthsmall<<endl;

return 0;
}```
`3rd smallest element = 21`
##### Java Program
```import java.io.*;
import java.util.*;

class tutorialCup
{
// function to find k-th largest element
// this function performs a binary search by value
// on the given matrix
static int kthSmallest(ArrayList<ArrayList<Integer>> mat,int k)
{
int n = mat.size();

if(k == 0 || k > n*n || n == 0)
return -1;

if(k == 1)
return mat.get(0).get(0);

// define smallest and largest element in the matrix as
// lower range &
// upper range
int lo = mat.get(0).get(0);
int hi = mat.get(n-1).get(n-1);

// perform binary search (by value)
// between smallest(top-left) and largest(bottom-down) values
while (lo < hi)
{
int mid = lo + (hi - lo) / 2;
int count = 0;
int j = n - 1;

// find out how many numbers are greater than mid
// between lo and hi
for (int i = 0; i < n; i++)
{
while (j >= 0 && mat.get(i).get(j) > mid)
j--;

count += (j + 1);
}

// if number of such element is less than k
// narrow the search range by increasing lo value
if (count < k)
lo = mid + 1;
// if number of such element is greater or equal to k
// narrow the search range by decreasing hi value
else
hi = mid;
}

// after iteratively narrowing the search range
// you narrow down to a single element in the matrix
// which is k-th smallest element
return lo;
}

public static void main (String[] args)
{
ArrayList<ArrayList<Integer>> mat = new ArrayList<ArrayList<Integer>>();

int k = 3;
int kthsmall = kthSmallest(mat,k);

if(kthsmall == -1)
System.out.println("3rd smallest element doesn't exist.");
else
System.out.println("3rd smallest element = "+kthsmall);

}
}```
`3rd smallest element = 21`

#### Complexity Analysis

• Time Complexity : T(n) = O(nlog(max-min)) = O(nlog(const)) = O(n), here max-min is the difference between largest and smallest values in the matrix.Since both are integers, the maximum difference can’t be more than INT_MAX, so essentially max-min becomes constant.
• Space Complexity : A(n) = O(1)

References

Translate »