How to find Kth smallest element in a Sorted Matrix!?

Tease by Leetcode!!

Given an n x n matrix where each of the rows and columns is sorted in ascending order, return the kth smallest element in the matrix.

Binary Search is always levied on a sorted list, so we need something sorted here. But it’s really hard to get an intuition on what to apply Binary Search on, so here comes a thought for food, we do know that our answer, kth smallest element will be the one for which the count of elements, less than or equal to it will be ‘k’. And that element is going to be an element from the already given matrix.

        int n = matrix.size();
int low = matrix[0][0], high = matrix[n-1][n-1];

while(low < high) {
int mid = low + (high - low)/2;

if(count(matrix, mid) < k) low = mid + 1;
else high = mid;

}
1    5    7
10 11 13
12 14 18
int kthSmallest(vector<vector<int>>& matrix, int k) {
int n = matrix.size();
int low = matrix[0][0], high = matrix[n-1][n-1];

while(low < high) {
int mid = low + (high - low)/2;

if(count(matrix, mid) < k) low = mid + 1;
else high = mid;

}

return low;
}
int count(vector<vector<int>>& grid, int mid) {
int count = 0, n = grid.size();

for(int i=0; i<n; i++) {
for(int j = 0; j<n && grid[i][j] <= mid; j++) count++;
}

return count;
}

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Abhishek Gururani

Abhishek Gururani

I write articles on Android Development, and problem solving.