public int kthSmallest(int[][] matrix, int k) {
if (matrix.length == 0) {
return 1;
}
TreeSet<Integer> set = new TreeSet<Integer>();
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i = 0; i < matrix.length; i++) {
for(int j = 0; j < matrix[0].length; j++) {
set.add(matrix[i][j]);
map.put(matrix[i][j], map.getOrDefault(matrix[i][j], 0) + 1);
}
}
Iterator<Integer> it = set.iterator();
int result = 1, i = 0;
while(it.hasNext() && i < k) {
result = it.next();
i += map.get(result);
}
return result;
}
HashMap + TreeSet approach. Java. O(n^2*logn(n)) time and O(n^2) space complexity.


@StefanPochmann good to have people who can correct)) TreeSet make add operation in logN time. It means that I have O(n^2*logN) time complexity. And yes it is O(n^2) space. i it is just iterator to check that it is kth element.