Java and Python Solutions with and without Tables


  • 38
    S

    Given A and B are sparse matrices, we could use lookup tables to speed up. At the beginining I thought two lookup tables would be necessary. After discussing with @yavinci, I think one lookup table for B would be enough. Surprisingly, it seems like detecting non-zero elements for both A and B on the fly without additional data structures provided the fastest performance on current test set.

    However, I think such fastest performance could due to an imperfect test set we have for OJ right now: there are only 12 test cases. And, for an element B[k, j], it would be detected for non-zero elements several times if we detecting both A and B on the fly, depending on how many i's make elements A[i, k] non-zero. With this point, the additional data structures, like lookup tables, should save our time by focusing on only non-zero elements. If it is not, I am worried the set of OJ test cases probably is not good enough.

    Anyway, I am posting my respective solutions below. Comments are welcome. Thanks @yavinci again for discussing with me.

    Python solution with only one table for B (~196ms):

    class Solution(object):
        def multiply(self, A, B):
            """
            :type A: List[List[int]]
            :type B: List[List[int]]
            :rtype: List[List[int]]
            """
            if A is None or B is None: return None
            m, n, l = len(A), len(A[0]), len(B[0])
            if len(B) != n:
                raise Exception("A's column number must be equal to B's row number.")
            C = [[0 for _ in range(l)] for _ in range(m)]
            tableB = {}
            for k, row in enumerate(B):
                tableB[k] = {}
                for j, eleB in enumerate(row):
                    if eleB: tableB[k][j] = eleB
            for i, row in enumerate(A):
                for k, eleA in enumerate(row):
                    if eleA:
                        for j, eleB in tableB[k].iteritems():
                            C[i][j] += eleA * eleB
            return C
    

    Java solution with only one table for B (~150ms):

    public class Solution {
        public int[][] multiply(int[][] A, int[][] B) {
            if (A == null || A[0] == null || B == null || B[0] == null) return null;
            int m = A.length, n = A[0].length, l = B[0].length;
            int[][] C = new int[m][l];
            Map<Integer, HashMap<Integer, Integer>> tableB = new HashMap<>();
            
            for(int k = 0; k < n; k++) {
                tableB.put(k, new HashMap<Integer, Integer>());
                for(int j = 0; j < l; j++) {
                    if (B[k][j] != 0){
                        tableB.get(k).put(j, B[k][j]);
                    }
                }
            }
    
            for(int i = 0; i < m; i++) {
                for(int k = 0; k < n; k++) {
                    if (A[i][k] != 0){
                        for (Integer j: tableB.get(k).keySet()) {
                            C[i][j] += A[i][k] * tableB.get(k).get(j);
                        }
                    }
                }
            }
            return C;   
        }
    }
    

    Python solution without table (~156ms):

    class Solution(object):
        def multiply(self, A, B):
            """
            :type A: List[List[int]]
            :type B: List[List[int]]
            :rtype: List[List[int]]
            """
            if A is None or B is None: return None
            m, n, l = len(A), len(A[0]), len(B[0])
            if len(B) != n:
                raise Exception("A's column number must be equal to B's row number.")
            C = [[0 for _ in range(l)] for _ in range(m)]
            for i, row in enumerate(A):
                for k, eleA in enumerate(row):
                    if eleA:
                        for j, eleB in enumerate(B[k]):
                            if eleB: C[i][j] += eleA * eleB
            return C
    

    Java solution without table (~70ms):

    public class Solution {
        public int[][] multiply(int[][] A, int[][] B) {
            int m = A.length, n = A[0].length, l = B[0].length;
            int[][] C = new int[m][l];
    
            for(int i = 0; i < m; i++) {
                for(int k = 0; k < n; k++) {
                    if (A[i][k] != 0){
                        for (int j = 0; j < l; j++) {
                            if (B[k][j] != 0) C[i][j] += A[i][k] * B[k][j];
                        }
                    }
                }
            }
            return C;   
        }
    }
    

    Python solution with two tables (~196ms):

    class Solution(object):
        def multiply(self, A, B):
            """
            :type A: List[List[int]]
            :type B: List[List[int]]
            :rtype: List[List[int]]
            """
            if A is None or B is None: return None
            m, n = len(A), len(A[0])
            if len(B) != n:
                raise Exception("A's column number must be equal to B's row number.")
            l = len(B[0])
            table_A, table_B = {}, {}
            for i, row in enumerate(A):
                for j, ele in enumerate(row):
                    if ele:
                        if i not in table_A: table_A[i] = {}
                        table_A[i][j] = ele
            for i, row in enumerate(B):
                for j, ele in enumerate(row):
                    if ele:
                        if i not in table_B: table_B[i] = {}
                        table_B[i][j] = ele
            C = [[0 for j in range(l)] for i in range(m)]
            for i in table_A:
                for k in table_A[i]:
                    if k not in table_B: continue
                    for j in table_B[k]:
                        C[i][j] += table_A[i][k] * table_B[k][j]
            return C
    

    Java solution with two tables (~160ms):

    public class Solution {
        public int[][] multiply(int[][] A, int[][] B) {
            if (A == null || B == null) return null;
            if (A[0].length != B.length) 
                throw new IllegalArgumentException("A's column number must be equal to B's row number.");
            Map<Integer, HashMap<Integer, Integer>> tableA = new HashMap<>();
            Map<Integer, HashMap<Integer, Integer>> tableB = new HashMap<>();
            int[][] C = new int[A.length][B[0].length];
            for (int i = 0; i < A.length; i++) {
                for (int j = 0; j < A[i].length; j++) {
                    if (A[i][j] != 0) {
                        if(tableA.get(i) == null) tableA.put(i, new HashMap<Integer, Integer>());
                        tableA.get(i).put(j, A[i][j]);
                    }
                }
            }
            
            for (int i = 0; i < B.length; i++) {
                for (int j = 0; j < B[i].length; j++) {
                    if (B[i][j] != 0) {
                        if(tableB.get(i) == null) tableB.put(i, new HashMap<Integer, Integer>());
                        tableB.get(i).put(j, B[i][j]);
                    }
                }
            }
            
            for (Integer i: tableA.keySet()) {
                for (Integer k: tableA.get(i).keySet()) {
                    if (!tableB.containsKey(k)) continue;
                    for (Integer j: tableB.get(k).keySet()) {
                        C[i][j] += tableA.get(i).get(k) * tableB.get(k).get(j);
                    }
                }
            }
            return C;
        }
    }
    

  • 1
    S

    what is the time complexity of these methods please?


  • 1

    One potential advantage of having two hash tables is that it can be used as a sparse matrix representation. The the code becomes more reusable and extensible.


  • 0
    M

    @stpeterh How about this? If we traverse A column by column instead of row by row then we don't need to use a HashMap:

    import java.util.*;
    
    public class Solution {
    
    
        public int[][] multiply(int[][] A, int[][] B) {
            if (A == null || A[0] == null || B == null || B[0] == null) return null;
            int m = A.length, n = A[0].length, l = B[0].length;
            int[][] C = new int[m][l];
            
            //for each column in A
            for(int k = 0; k < n; k++) {
    
                //compute the non-zero slots in row k in B:
                LinkedList<BSlot> nonZerosInB = nonZerosInRowKInB(B, k);
    
                //for each slot in column k in A
                for(int i = 0; i < m; i++) {  
    
                    if(A[i][k] != 0) {
                        //for each non-zero slot in row k in B
                        for(BSlot bSlot: nonZerosInB) {
                            C[i][bSlot.j] += A[i][k] * bSlot.value;
                        }
                    }
                }
            }
    
            return C;   
        }
    
        //returns linked list of non-zeros in B's row k
        LinkedList<BSlot> nonZerosInRowKInB(int[][] B, int k) {
            //compute the non-zero slots in row k in B:
            LinkedList<BSlot> nonZerosInB = new LinkedList<>();
    
            //for each slot in row k in B
            for(int j = 0; j < B[0].length; j++) {
                if (B[k][j] != 0){
                    //we need to save the column (j) and the value of the slot (B[k][j])
                    BSlot bSlot = new BSlot(j, B[k][j]);
                    nonZerosInB.add(bSlot);
                }
            }    
            return nonZerosInB;
        }
    
    }
    
    //non-zero slot in matrix B
    class BSlot {
        int j; //column 
        int value; 
    
        BSlot(int j, int value) {
            this.j = j;
            this.value = value;
        }
    }
    

  • 0

    @stpeterh
    Hello, why dose the tag contain HashTable, I didn't see the advantage of it.
    I fount this post, with or without table, the time complexity is still O(n^3).
    Than why we wanna extra space?
    https://discuss.leetcode.com/topic/30625/easiest-java-solution/9


  • 0

    HashMap can reduce the theoretic complexity, however HashMap in Java is relatively slow, I think it is why the first solution is slower than second one.


  • 0
    L

    Hi, I think because you still need to go through the whole matrix A, so the final complexity is at least m*n (suppose A is m*n, B is n*l)

    Why not choose the element of A by the active cell of B instead. Suppose for a sparse matrix, the avg number of active cell in a column is less than 1. Now we only have l column active numbers. We can now pick the corresponding number from A for less than l times for m rows, which is less than m*l times in total. Well, it depends on how sparse the matrix is.

    Tell me if I am wrong.


  • 0
    Y
    This post is deleted!

  • 1
    M

    Java solution with only one table for A ~155ms

    public class Solution {
        public int[][] multiply(int[][] A, int[][] B) {
            int m = A.length, g = A[0].length, n = B[0].length;
            Map<Integer, HashMap<Integer, Integer>> mapA = new HashMap<>();
            int[][] c = new int[m][n];
            // Map<Integer, HashMap<Integer, Integer>> mapB = new HashMap<>();
            // add matrix A
            for (int i = 0; i < m; ++i) {
                HashMap<Integer, Integer> tmp = new HashMap<>();
                for (int j = 0; j < g; ++j) {
                    if (A[i][j] != 0) tmp.put(j, A[i][j]);
                }
                mapA.put(i, tmp);
            }
            // Multiplication
            for (int i = 0; i < m; ++i) {
                HashMap<Integer, Integer> tmp = mapA.get(i);
                for (Integer k : tmp.keySet()) {
                     for (int j = 0; j < n; ++j) c[i][j] += tmp.get(k) * B[k][j];
                }
            }
            return c;
        }
    }
    

  • 0
    F

    Nice explanations. It is even better if we can use a convert method to preprocess A and B to reduce redundant code.
    Anyone who can figure out the time complexity of the 3 approaches? You can make assumption such as for a nXn sparse matrix, it
    has O(n) nonzero elements and start to derive big O from there.

    public class Solution {
        public int[][] multiply(int[][] a, int[][] b) {
            int m = a.length;
            int nB = b[0].length;
            int[][] c = new int[m][nB];
            Map<Integer, Map<Integer, Integer>> mapA = convert(a);
            Map<Integer, Map<Integer, Integer>> mapB = convert(b);
            for (int i : mapA.keySet()) {
                for (int k : mapA.get(i).keySet()) {
                    if (!mapB.containsKey(k)) {
                        continue;
                    }
                    for (int j : mapB.get(k).keySet()) {
                        c[i][j] += mapA.get(i).get(k) * mapB.get(k).get(j);
                    }
                }
            }
            return c;
        }
        
        private Map<Integer, Map<Integer, Integer>> convert(int[][] matrix) {
            int m = matrix.length;
            int n = matrix[0].length;
            Map<Integer, Map<Integer, Integer>> map = new HashMap<>();
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (matrix[i][j] == 0) {
                        continue;
                    }
                    map.putIfAbsent(i, new HashMap<>());
                    map.get(i).put(j, matrix[i][j]);
                }
            }
            return map;
        }
    }
    

  • -1
    This post is deleted!

  • 0
    H

    I think you should store the nonzero elements of B by column instead of row


Log in to reply
 

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