# HashMap + TreeSet approach. Java. O(n^2*logn(n)) time and O(n^2) space complexity.

• ``````
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++) {
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;
}
``````

• Do you really think `TreeSet.add` takes only O(1) time?

• Also, O(n) space?? And why adding values into `i`?

• @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 k-th element.

• i it is just iterator to check that it is k-th element.

Ah, right, I'd say you're doing it a bit strangely and so I wasn't looking at the right place(s). But I should have.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.