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

There are a couple of ways to solve this problem, more widely used is the one using a Heap Data Structure. Whose TC: O(N*N*logk), and SC: O(k), where k is the size of Heap that we maintain during the process.

But what intrigued me into writing the solution of this problem was this follow up challenge by Leetcode :

Tease by Leetcode!!

As the entire matrix was sorted, I thought of using the cute Binary Search, but it was not that straightforward.

And hence I’m writing this tutorial to show you how to do that using a Binary Search, but mind you it’s not gonna be your regular Binary Search next door. It’s what we mates call “B.B.S.”, Backchod Binary Search.

Problem statement :

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.

So we can apply our Binary Search in the range minElement(matrix[0][0]), and maxElement(matrix[n-1][n-1]). And the smallest element for which the count of elements, less than or equal to it will be ‘k’, will be our answer.

But what will be the traversing condition of our Binary Search? that will be the count of elements smaller or equal to our chosen element.

        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;

}

Let’s consider a case :

example matrix :

1    5    7
10 11 13
12 14 18

suppose we need to find the 3rd smallest element,

case1 :

our mid is 6, no. of elements smaller or equal to 6 are : 2(1, 5), this means that 6 or elements smaller than 6, will never be our answer, so we’ll remove 6 and lower elements from our Binary Search : low = 6 + 1

case2 :

our mid is 8, no. of elements smaller or equal to 8 are : 3, this doesn’t mean 8 is our answer, but it means that 8 could be our possible answer. The answer might also be a number less than 8 : high = 8.

Solution :

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

Complexity Analysis :

TC: O(N*N*log(range of low — high))

SC: O(1)

This marks the end of our short tutorial to find the Kth smallest element in a sorted matrix, by using Backchod Binary Search.

--

--

I write articles on Android Development, and problem solving.

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