Leetcode #311. Sparse Matrix Multiplication

[yokostan]

With HashTable, we should wrap one HashTable as value in an outer HashTable, runtime beats 61%:

class Solution {
    public int[][] multiply(int[][] A, int[][] B) {
        int[][] res = new int[A.length][B[0].length];
        if (A == null || B == null || A.length == 0 || B.length == 0 || A[0].length == 0 || B[0].length == 0) return res;

        Map<Integer, HashMap<Integer, Integer>> map = new HashMap<>();

        for (int i = 0; i < A[0].length; i++) {
            map.put(i, new HashMap<Integer, Integer>());
            for (int j = 0; j < B[0].length; j++) {
                if (B[i][j] == 0) continue;
                map.get(i).put(j, B[i][j]);
            }
        }

        for (int i = 0; i < A.length; i++) {
            for (int k = 0; k < A[0].length; k++) {
                if (A[i][k] == 0) continue;
                for (Integer j : map.get(k).keySet()) {
                    res[i][j] += A[i][k] * map.get(k).get(j);
                }
        }
        }

        return res;
    }
}

The above method is just multiplying A of dimension i, k with B of dimension k, j. As column of A equals row of B, we only need to store the B[k][j] values for corresponding i, j for later use.

Due to the test cases, brute force is the fastest now:

class Solution {
    public int[][] multiply(int[][] A, int[][] B) {
        int[][] res = new int[A.length][B[0].length];
        if (A == null || B == null || A.length == 0 || B.length == 0 || A[0].length == 0 || B[0].length == 0) return res;

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

        return res;
    }
}