Kth Smallest Element in a Sorted Matrix

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Example:

matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,

return 13.

Note: You may assume k is always valid, 1 ≤ k ≤ n2.

// PQ Solution
public class Solution {
    static class Pair {
        int row, col, val;

        public Pair(int x, int y, int val) {
            this.row = x;
            this.col = y;
            this.val = val;
        }
    }

    public int kthSmallest(int[][] matrix, int k) {
        // n*n matrix
        int n = matrix.length;
        PriorityQueue<Pair> pq = new PriorityQueue<Pair>((a, b) -> a.val - b.val);
        for (int j = 0; j < n; j++)
            pq.add(new Pair(0, j, matrix[0][j]));
        for (int i = 0; i < k - 1; i++) {
            Pair t = pq.poll();
            if (t.row == n - 1)
                continue;
            pq.add(new Pair(t.row + 1, t.col, matrix[t.row + 1][t.col]));
        }
        return pq.poll().val;
    }
}

// Binary Search Solution
public 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 < hi) {
            int mid = lo + (hi - lo) / 2;
            // Finding number of elements <= mid
            int count = 0, j = matrix[0].length - 1;
            for (int i = 0; i < matrix.length; i++) {
                while (j >= 0 && matrix[i][j] > mid)
                    j--;
                count += (j + 1);
            }
            if (count < k)
                lo = mid + 1;
            else
                hi = mid;
        }
        return lo;
    }
}