C++ solution using Binary Search easy to follow


  • 0
    G
    class Solution {
    public:
        int kthSmallest(vector<vector<int>>& matrix, int k) {
            
            int start = matrix[0][0];
            int mRows = matrix.size();
            int mCols = matrix[matrix.size() - 1].size();
            int end = matrix[mRows - 1][mCols - 1] + 1;
            
            while(start < end){
                int med = (start + (end - start)/2);
                int count = 0;
                
                for(int i = 0; i < mRows; ++i){
                    auto ub = upper_bound(matrix[i].begin(),matrix[i].end(),med);
                    count += distance(matrix[i].begin(),ub);
                }
                
                if(count >= k){
                    end = med;
                }
                else{
                    start = med  + 1;
                }
            }
            
            return start;
        }
    };
    

Log in to reply
 

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