Kth Smallest Number in Sorted Matrix

Find the _k_th smallest number in at row and column sorted matrix.

Example

Given k =4and a matrix:

[
  [1 ,5 ,7],
  [3 ,7 ,8],
  [4 ,8 ,9],
]

return5.

class Number {
    int x;
    int y;
    int val;
    public Number(int x, int y, int val) {
        this.x = x;
        this.y = y;
        this.val = val;
    }
}
class NumComparator implements Comparator<Number> {
    @Override
    public int compare(Number n1, Number n2) {
        return n1.val - n2.val;
    }
}
public int kthSmallest(int[][] matrix, int k) {
    if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        return -1;
    }
    int[] dx = new int[]{1, 0};
    int[] dy = new int[]{0, 1};
    PriorityQueue<Number> minHeap = new PriorityQueue<Number>(k, new NumComparator());
    boolean[][] hash = new boolean[matrix.length][matrix[0].length];
    minHeap.offer(new Number(0, 0, matrix[0][0]));
    for(int i = 0; i < k - 1; i++) {
        Number tmp = minHeap.poll();
        for(int j = 0; j < 2; j++) {
            int nx = tmp.x + dx[j];
            int ny = tmp.y + dy[j];
            if(nx >= 0 && nx < matrix.length && ny >= 0 && ny < matrix[0].length && !hash[nx][ny]) {
                hash[nx][ny] = true;
                minHeap.offer(new Number(nx, ny, matrix[nx][ny]));
            }
        }
    }
    return minHeap.peek().val;
}