class Solution
{
public:
int kthSmallest(vector<vector<int>>& matrix, int k)
{
int n = matrix.size();
int le = matrix[0][0], ri = matrix[n  1][n  1];
int mid = 0;
while (le < ri)
{
mid = le + (rile)/2;
int num = 0;
for (int i = 0; i < n; i++)
{
int pos = upper_bound(matrix[i].begin(), matrix[i].end(), mid)  matrix[i].begin();
num += pos;
}
if (num < k)
{
le = mid + 1;
}
else
{
ri = mid;
}
}
return le;
}
};
My solution using Binary Search in C++


@StefanPochmann
Yes,you're right.
There are some parts of this code should be improved. Thank you very very much.

@agave
The complexity of my solution is O(nlog(n)log(N)), n is the number of rows.
This is my first time to share my code and my variable name are so thoughtless.
Thank you for correcting me. I will do better next time.

@光速小子 said in My solution using Binary Search in C++:
@agave
The complexity of my solution is O(rlogn), r is the number of rows.Better don't redefine names. The problem statement already defined n to be the number of rows (and columns).
I will do better next time.
You can also edit your post and do better this time :)



Easier to read C++ implementation according to your idea:
int kthSmallest(vector<vector<int>>& matrix, int k) { int n = matrix.size(); int left = matrix[0][0]; int right = matrix[n1][n1]; while (left < right) { int midv = (left + right) / 2; int count = 0; // number of elements no bigger than midv for (int i = 0; i < n; i++) { vector<int>& row = matrix[i]; count += std::upper_bound(row.begin(), row.end(), midv)  row.begin(); } if (count < k) { left = midv + 1; } else { right = midv; } } return left; }


The time complexity is O(n * log(n) * log(N)), where N is the search space that ranges from the smallest element to the biggest element.
You can argue that
int
implies N = 2^32, so log(N) is constant. I guess this is where O(n * log(n)) comes from.I thought this idea was weird for a while. Then I noticed the previous problem 377. Combination Sum IV is pretty much doing the same thing, so this idea may actually be intended. Nice one!

Thanks for the solution. Java version. Thanks @StefanPochmann 's comment.
int n = matrix.length; int left = matrix[0][0], right = matrix[n  1][n  1]; while (left < right) { int mid = (left + right) / 2; int count = 0; // number of elements no bigger than mid for (int i = 0; i < n; i++) { int[] row = matrix[i]; int t_left = 0, t_right = row.length; while (t_left < t_right) { int t_mid = (t_left + t_right) / 2; int value = row[t_mid]; if(value > mid) { t_right = t_mid; } else { t_left = t_mid + 1; } } count += t_left; } if (count < k) { left = mid + 1; } else { right = mid; } } return left;

@jianqing The inner part should be binary search, too. At least
upper_bound
is.

Actually, the inner part can be done in
O(n)
time.class Solution { public: int kthSmallest(vector<vector<int>>& matrix, int k) { int n=matrix.size(); int l=matrix[0][0], r=matrix[n1][n1], mid; while(l<r){ mid=l+r>>1; int cnt=0, j=n1; for(int i=0;i<n;i++){ while(j>=0&&matrix[i][j]>mid) j; cnt+=j+1; } if(cnt<k) l=mid+1; else r=mid; } return l; } };

@storypku hi, thanks for your sharing.
I have a question: you return "left" in the last line. But how do u know the "left" is a value in the matrix?

