@@ -0,0 +1,1472 @@
+package com.freetymekiyan.algorithms.level.medium;%0A%0A/**%0A * Given two sparse matrices A and B, return the result of AB.%0A * %3Cp%3E%0A * You may assume that A's column number is equal to B's row number.%0A * %3Cp%3E%0A * Example:%0A * %3Cp%3E%0A * %7C A = %5B%0A * %7C   %5B 1, 0, 0%5D,%0A * %7C   %5B-1, 0, 3%5D%0A * %7C %5D%0A * %3Cp%3E%0A * %7C B = %5B%0A * %7C   %5B 7, 0, 0 %5D,%0A * %7C   %5B 0, 0, 0 %5D,%0A * %7C   %5B 0, 0, 1 %5D%0A * %7C %5D%0A * %3Cp%3E%0A * %7C      %7C  1 0 0 %7C   %7C 7 0 0 %7C   %7C  7 0 0 %7C%0A * %7C AB = %7C -1 0 3 %7C x %7C 0 0 0 %7C = %7C -7 0 3 %7C%0A * %7C                   %7C 0 0 1 %7C%0A * Company Tags: LinkedIn, Facebook%0A * Tags: Hash Table%0A */%0Apublic class SparseMatrixMultiplication %7B%0A%0A    /**%0A     * Matrix multiplication is row in A multiply column in B.%0A     * Loop through A row by row.%0A     * In each row, multiply the value in column with row in B.%0A     * Add it to the position of result.%0A     * Since the matrix is sparse, we can skip zeros.%0A     */%0A    public int%5B%5D%5B%5D multiply(int%5B%5D%5B%5D A, int%5B%5D%5B%5D B) %7B%0A        int mA = A.length;%0A        int nA = A%5B0%5D.length;%0A        int nB = B%5B0%5D.length;%0A        int%5B%5D%5B%5D res = new int%5BmA%5D%5BnB%5D;%0A        for (int i = 0; i %3C mA; i++) %7B%0A            for (int j = 0; j %3C nA; j++) %7B%0A                if (A%5Bi%5D%5Bj%5D != 0) %7B // Skip zero in A%0A                    for (int k = 0; k %3C nB; k++) %7B%0A                        if (B%5Bj%5D%5Bk%5D != 0) %7B // Skip zero in B%0A                            res%5Bi%5D%5Bk%5D += A%5Bi%5D%5Bj%5D * B%5Bj%5D%5Bk%5D;%0A                        %7D%0A                    %7D%0A                %7D%0A            %7D%0A        %7D%0A        return res;%0A    %7D%0A%7D%0A

add sparse matrix multiplication