311. Sparse Matrix Multiplication - cocoder39/coco39_LC GitHub Wiki

311. Sparse Matrix Multiplication

Intuitive solution:

class Solution:
    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:
        m, k, n = len(mat1), len(mat1[0]), len(mat2[0])
        
        res = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                for a in range(k):
                    res[i][j] += (mat1[i][a] * mat2[a][j])
        return res

Above solution doesn't leverage sparse matrix

class Solution:
    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:
        m, k, n = len(mat1), len(mat1[0]), len(mat2[0])
        
        res = [[0] * n for _ in range(m)]
        for i in range(m):
            for a in range(k):
                if mat1[i][a] == 0:
                    continue
                for j in range(n):
                    res[i][j] += (mat1[i][a] * mat2[a][j])
        return res

========================================================================

Trick: res[i][j] += A[i][k] * B[k][j] => iterate i and k first, or iterate k and j first, then we can check A[i][k] or B[k][j] before multiplication.

time complexity is O(A.size() * B.size() * B[0].size())

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < A[0].size(); k++) {
                    //if (! A[i][k] && ! B[k][j])
                    res[i][j] += A[i][k] * B[k][j];
                }
            }
        }

Initial idea was driven by the goal of getting the res[i][j] one by one. In that way, the sparse is of no use, and the run time would exceed. Change the order of for loop, making use of sparse though increasing res[i][j] step by step.

vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
        int m = A.size();
        int n = B[0].size();
        vector<vector<int>> res(m, vector<int>(n));
        
        for (int i = 0; i < m; i++) {
            for (int k = 0; k < B.size(); k++) {
                if (A[i][k] != 0) {
                    for (int j = 0; j < n; j++) {
                        res[i][j] += A[i][k] * B[k][j];
                    }
                }
            }
        }
        return res;
    }

a sparse matrix can be stored in hash table, time complexity of this method is O(sz1 * sz2 * sz3)

vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
        int sz1 = A.size();
        int sz2 = B.size();
        int sz3 = B[0].size();
        
        unordered_map<int, int> mpa;
        for (int i = 0; i < sz1; i++) {
            for (int j = 0; j < sz2; j++) {
                if (A[i][j] != 0)
                    mpa[i * sz2 + j] = A[i][j];
            }
        }
        
        unordered_map<int, int> mpb;
        for (int i = 0; i < sz2; i++) {
            for (int j = 0; j < sz3; j++) {
                if (B[i][j] != 0)
                    mpb[i * sz3 + j] = B[i][j];
            }
        }
        
        vector<vector<int>> res(sz1, vector<int>(sz3));
        for (auto &a : mpa) {
            int ar = a.first / sz2;
            int ac = a.first % sz2;
            for (int i = 0; i < sz3; i++) {
                if (mpb.find(ac * sz3 + i) != mpb.end()) {
                    res[ar][i] += a.second * mpb[ac * sz3 + i];
                }
            }
        }
        return res;
    }

fb interview: dot product of sparse vector unordered_map[idx] = val => O(n) time and O(m + n) memory, but hash table takes more memory overhead

vector<pair<idx, val>> => O(m + n) memory, O(m * n) time (iterate idx) -> O(n * log(m)) (binary search idx) -> O(n) time two pointers

int res = 0;
int i = 0, j = 0;
while (i < m && j < n) {
    if (A[i].first == B[j].first)    res += A[i].second * B[j].second;
    else if (A[i].first < B[j].first)    i++;
    else j++;
}
⚠️ **GitHub.com Fallback** ⚠️