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 :

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.