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


  • 0
    O
    
        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;
        }
    

  • 0

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


  • 0

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


  • 1
    O

    @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.


  • 0

    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.


Log in to reply
 

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