Why java solution using HashSet runs so slow?


  • 0
    H

    This solution requires O(k) space where k is the number of zeroes in the original matrix
    run time is O(N^2), can't be lower
    But why the actual run time is so slow (beats less than 10% of submissions)?
    Is it because accessing HashSet takes lots of time?

    public void setZeroes(int[][] matrix) {
            
            if (matrix == null || matrix.length == 0)
                return;
            int m = matrix.length;
            
            if (matrix[0] == null || matrix[0].length == 0)
                return;
                
            int n = matrix[0].length;
            
            HashSet<Integer> row = new HashSet<Integer>();
            HashSet<Integer> col = new HashSet<Integer>();
                
            for (int i = 0; i < m; i++) {
                 for (int j = 0; j < n; j++) {
                     if (matrix[i][j] == 0) {
                         row.add(i);
                         col.add(j);
                     }
                 }
            }
            
            for (int i = 0; i < m; i++) {
               for (int j = 0; j < n; j++) {
                   if (row.contains(i) || col.contains(j))
                        matrix[i][j] = 0;
               }
            }
        }

  • 0
    B

    IMHO: Yes. Go check Hashcode() function, they will add extra operations, that's the same reason we try to avoid to use for loop (map.get(key) + 1) they will call get() every time, it might o(1), but still need to hash() function to get the value(find the bucket). Array will always be the fastest data structure so far


Log in to reply
 

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