378

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int rows = matrix.size(), cols = matrix[0].size();
        int l=matrix[0][0], r = matrix[rows-1][cols-1];

        int ans = 0;
        while(l<r){
            int mid = (l+r)/2;
            int count = getCount(matrix, mid, rows, cols);
            if(count < k)
                l = mid+1;
            else
                r = mid;
        }
        return l;
    }

    int getCount(vector<vector<int>>& matrix, int k, int rows, int cols){
        int count = 0, curX = rows-1, curY = 0;
        while(curX >= 0 && curY < cols){
            if(matrix[curX][curY] > k)
                curX--;
            else{
                count += (curX+1);
                curY++;
            }
        }
        return count;
    }

};