Kth Smallest Element In A Sorted Matrix Problem Statement

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

Example One

{
"matrix": [
[1, 3, 5],
[2, 3, 6],
[3, 3, 7]
],
"k": 5
}

Output:

3

Example Two

{
"matrix": [
[2, 2],
[2, 3]
],
"k": 3
}

Output:

2

Notes

• Return the kth smallest element in the sorted order, not the kth distinct element.
• Find a solution with a memory complexity better than O(n2).

Constraints:

• 1 <= n <= 300
• -10⁵ <= any element of the matrix <= 10⁵
• All the rows and columns of matrix are guaranteed to be sorted in non-decreasing order.
• 1 <= k <= n2

Code For Kth Smallest Element In A Sorted Matrix Solution: Binary Search

/*
Asymptotic complexity in terms of the number of rows `M`, the number of columns, `N` and
highest difference between the numbers in the matrix `D`:
* Time: O((M + N) * log(D)).
* Auxiliary space: O(1).
* Total space: O(M * N).
*/

int m, n;
int count_less_or_equal(vector<vector<int>> &matrix, int x) {
    int cnt = 0, c = n - 1;
    for (int r = 0; r < m; r++) {
        while (c >= 0 && matrix[r][c] > x) c--;
        cnt += (c + 1);
    }
    return cnt;
}

int get_kth_smallest(vector<vector<int>> &matrix, int k) {
    m = matrix.size(), n = matrix[0].size();
    int left = matrix[0][0], right = matrix[m-1][n-1];
    int answer = -1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (count_less_or_equal(matrix, mid) >= k) {
            answer = mid;
            right = mid - 1;
        }
        else {
            left = mid + 1;
        }
    }
    return answer;
}

We hope that these solutions to kth smallest element in a sorted matrix problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart’s FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

• Back-end Engineering Interview Course
• Front-end Engineering Interview Course
• Full Stack Developer Interview Course

‍To learn more, register for the FREE webinar.