# 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 :

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 :

## 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.

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.*