Find the kth smallest number in at row and column sorted matrix.
Have you met this question in a real interview? Yes
Example
Given k = 4 and a matrix:
[
[1 ,5 ,7],
[3 ,7 ,8],
[4 ,8 ,9],
]
return 5
Challenge
Solve it in O(k log n) time where n is the bigger one between row size and column size.
Tags
Heap Priority Queue Matrix
Related Problems
Hard Kth Smallest Sum In Two Sorted Arrays
Medium Kth Largest Element
class Solution {
public:
/\*\*
\* @param matrix: a matrix of integers
\* @param k: an integer
\* @return: the kth smallest number in the matrix
\*/
int kthSmallest\(vector<vector<int> > &matrix, int k\) {
// write your code here
if \(matrix.empty\(\) \|\| matrix\[0\].empty\(\)\) {
return -1;
}
int n = matrix.size\(\), m = matrix\[0\].size\(\);
int start = matrix\[0\]\[0\], end = matrix\[n - 1\]\[m - 1\];
while \(start < end\) {
int mid = start + \(end - start >> 1\);
if \(getCount\(matrix, mid\) < k\) {
start = mid + 1;
} else {
end = mid;
}
}
return start;
}
int getCount\(vector<vector<int>>& matrix, int val\) {
int cnt = 0, n = matrix.size\(\), m = matrix\[0\].size\(\);
int i = 0, j = m - 1;
while \(i < n && j >= 0\) {
if \(matrix\[i\]\[j\] > val\) {
--j;
} else {
cnt += j + 1;
++i;
}
}
return cnt;
}
};