Kth Smallest Element in a Sorted Matrix

So I am working on a Leetcode question and my code works for some cases but fails for certain cases.

Here is the question:

> 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

My approach is to use a minHeap, even if it stated that the array is sorted I still needed to make sure that I have it sorted from least to greatest value.

Here is my code:

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int row = matrix.length;
        int col = matrix[0].length;
        int result = 0;

        HashMap<Integer, Integer> map = new HashMap<>();
        //populate HashMap 
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                map.put(matrix[i][j],
                        map.getOrDefault(matrix[i][j], 0) + 1);
            }
        }

        PriorityQueue<Map.Entry<Integer, Integer>> pq =
                new PriorityQueue<>((n1, n2) -> n1.getValue() - n2.getValue());

        pq.addAll(map.entrySet());

        for (int i = 0; i < k && !(pq.isEmpty()); i++) {
            result = pq.poll().getKey();
        }

        return result;
    }
}

Here are my inputs:

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

Input 2: [[1,2],[1,3]] 
k = 1 

Here are the outputs:

Output 1: 13
Output 2: 2

Notice that the code works just fine for my first input where the 8th smallest element in the 2d-array is 13, but for the second input, the code is returning 2 as my first smallest element rather than returning 1.

Can someone please help me fix the code? I ask that you please not implement some fancy shorthand sorting technique e.g. Arrays.sort... it's not ideal for me as I am trying to learn how to implement heaps. Thanks a bunch

For solving this problem we can also binary search (a bit more efficient):

public class Solution {
    public static final int kthSmallest(final int[][] matrix, final int k) {
        int lo = matrix[0][0];
        int hi = matrix[matrix.length - 1][matrix[0].length - 1] + 1;

        while (lo < hi) {
            final int mid = lo + (hi - lo) / 2;
            int count = 0;
            int col = matrix[0].length - 1;

            for (int row = 0; row < matrix.length; ++row) {
                while (col >= 0 && matrix[row][col] > mid) {
                    col--;
                }
                count += (col + 1);
            }
            if (count < k) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }
}

You can use the flatMapToInt method to iterate over the rows of a 2d array in one stream:

public static void main(String[] args) {
    int[][] matrix1 = {{1, 5, 9}, {10, 11, 13}, {12, 13, 15}};
    int[][] matrix2 = {{1, 2}, {1, 3}};

    System.out.println(kthSmallest(matrix1, 8)); // 13
    System.out.println(kthSmallest(matrix2, 1)); // 1
}

public static int kthSmallest(int[][] matrix, int k) {
    return Arrays.stream(matrix)
            .flatMapToInt(Arrays::stream)
            .skip(k - 1)
            .findFirst()
            .getAsInt();
}

public static int kthSmallest(int[][] matrix, int k) {
    return Arrays
            .stream(matrix)
            .flatMapToInt(x -> Arrays.stream(x))
            .sorted()
            .skip(k-1)
            .findFirst()
            .getAsInt();
}

public static int kthSmallestNumber(int[][] matrix, int k) {
		
		return Arrays.stream(matrix).flatMapToInt(x->Arrays.stream(x))
				.distinct()
				.sorted()
				.skip(k-1)
				.findFirst()
				.getAsInt();
		
	}