Leetcode #378 Kth Smallest Element in a Sorted Matrix

[yokostan]

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int lo = matrix[0][0], hi = matrix[matrix.length - 1][matrix[0].length - 1];
        while (lo + 1 < hi) {
            int mid = (hi - lo) / 2 + lo;

            if (countLessEqual(matrix, mid) == k) {
                hi = mid;
            }
            else if (countLessEqual(matrix, mid) < k) {
                lo = mid;
            }
            else hi = mid;
        }  

        if (countLessEqual(matrix, lo) >= k) return lo;
        return hi;
    }

    private int countLessEqual(int[][] matrix, int mid) {
        int count = 0;
        int i = 0, j = matrix.length - 1;
        while (i < matrix.length && j >= 0) {
            if (matrix[i][j] <= mid) {
                count += j + 1;
                i++;
            }
            else j--;
        }
        return count;
    }
}