My solution using Binary Search in C++


  • 56
    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 + (ri-le)/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;
    	}
    };
    

  • 5

    @光速小子 what is the complexity of your solution? Your code could be cleaner and may need better variable names.


  • 4

    Fails matrix=[[2000000000]], k=1. Better start with INT_MIN/INT_MAX or matrix[0][0]/matrix[n-1][n-1]. But nice solution.


  • 1

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


  • 1

    @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.


  • 4

    @光速小子 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 :-)


  • 1

    @StefanPochmann
    I didn't know I can edit it...Sorry for that.
    I am editing it now.


  • 1

    @StefanPochmann
    I think this time the code is clearer.


  • 13
    S

    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[n-1][n-1];
            
            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;
        }
    
    

  • 1

    @storypku thank you.


  • 4
    O

    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!


  • 3
    J

    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;

  • 1

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


  • 0
    R
    This post is deleted!

  • 33
    Q

    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[n-1][n-1], mid;
            while(l<r){
                mid=l+r>>1;
                int cnt=0, j=n-1;
                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;
        }
    };
    

  • 11
    C

    @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?

  • 0
    H

    @csxuejin got the same question for this solution.


  • 14
    O

    @csxuejin @hudaiqiangmail-com

    Because the loop invariant is left<=Solution<=right. The moment it quits the loop, we also know another condition is true: left>=right.

    left<=Solution<=right and left>=right means left==Solution==right.


  • 0
    H

    @o_sharp Clear now. Thanks:)


  • 0

    I like this solution, but I'm a little confused. I always thought you couldn't do binary search on this sort of matrix - which was why we have to use saddleback searching. Can someone help correct my misunderstanding?


Log in to reply
 

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