Sparse Matrix Multiplication

Given two sparse matrices A and B, return the result of AB.

You may assume that A's column number is equal to B's row number.

Example:

A = [
  [ 1, 0, 0],
  [-1, 0, 3]
]

B = [
  [ 7, 0, 0 ],
  [ 0, 0, 0 ],
  [ 0, 0, 1 ]
]


     |  1 0 0 |   | 7 0 0 |   |  7 0 0 |
AB = | -1 0 3 | x | 0 0 0 | = | -7 0 3 |
                  | 0 0 1 |

Record all 0 row/col to avoid useless multiplication

    public int[][] multiply(int[][] A, int[][] B) {

        int [][]res = new int[A.length][B[0].length];
        boolean []rowA = new boolean[A.length];
        boolean []colB = new boolean[B[0].length];

        for(int i = 0 ; i < A.length; i++){
            for(int j = 0 ; j < A[0].length; j++)
                if(A[i][j] != 0){
                    rowA[i] = true;
                    break;
                }
        }
        for(int j = 0 ; j < B[0].length; j++){
            for(int i = 0 ; i < B.length; i++)
                if(B[i][j] != 0){
                    colB[j] = true;
                    break;
                }
        }

        for(int i = 0 ; i < A.length; i ++){
            for(int k = 0 ; k < B[0].length ; k ++){
                if(!rowA[i] || !colB[k]){
                    res[i][k] = 0;
                    continue;
                }

                int sum = 0;
                for(int j = 0 ; j < A[0].length; j ++){
                    sum += A[i][j] * B[j][k];
                }
                res[i][k] = sum;
            }
        }
        return res;
    }

results matching ""

    No results matching ""