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
- -105 <= any element of the matrix <= 105
- 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:
To learn more, register for the FREE webinar.
.png)
