# My thought with binary search

• ``````class Solution {
public:
int judge(vector<vector<int>>& matrix, int x, int k) {
int n = matrix.size(), m = matrix[0].size() - 4;
int sm = 0, nb = 0;
//printf("x=%d\n", x);
for(int i = 0; i < n; i++) {
int l = matrix[i][m], r = matrix[i][m + 1];
//printf("i=%d, l=%d, r=%d\n", i, l, r);
// get the number of elements in row i that not smaller than x
int L = l, R = r, res = l - 1;
while(l <= r) {
int mid = l + r >> 1;
if(matrix[i][mid] <= x) {
l = mid + 1;
res = mid;
}
else r = mid - 1;
}
matrix[i][m + 2] = res;
nb += res + 1;
res = L - 1;
// get the number of elements in row i that smaller than x
l = L; r = R;
while(l <= r) {
int mid = l + r >> 1;
if(matrix[i][mid] < x) {
l = mid + 1;
res = mid;
}
else r = mid - 1;
}
matrix[i][m + 3] = res;
sm += res + 1;
//printf("sm=%d, nb=%d\n", sm, nb);
}
if(nb >= k && sm < k) return 0;
else if(nb < k) {
for(int i = 0; i < n; i++) {
matrix[i][m] = matrix[i][m + 2] + 1;
}
return 1;
}
else {
for(int i = 0; i < n; i++) {
matrix[i][m + 1] = matrix[i][m + 3];
}
return -1;
}
}
int kthSmallest(vector<vector<int>>& matrix, int k) {
int n = matrix.size(), m = matrix[0].size();
for(int i = 0; i < n; i++) {
matrix[i].push_back(0);
matrix[i].push_back(m - 1);
matrix[i].push_back(0);
matrix[i].push_back(0);
}
int l = matrix[0][0], r = matrix[n - 1][m - 1];
int ans = 0;
while(l <= r) {
int mid = l * 1LL + r >> 1, ret;
if((ret = judge(matrix, mid, k)) == 0) {
ans = mid;
break;
}
else if(ret == 1) l = mid + 1;
else r = mid - 1;
}
return ans;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.