Sparse Matrix Multiplication

• Lintcode : 654
• Level : Medium

Problem

Given two Sparse Matrix A and B, return the result of AB.

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

Example
Example1

Input: 
[[1,0,0],[-1,0,3]]
[[7,0,0],[0,0,0],[0,0,1]]
Output:
[[7,0,0],[-7,0,3]]
Explanation:
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 |
Example2

Input:
[[1,0],[0,1]]
[[0,1],[1,0]]
Output:
[[0,1],[1,0]]

Concept & Algorithm

筆記

Time Complexity & Space Complexity

time : O(max(r c))
space: O(rA cB)

Answer

class Solution {
public:
    vector<vector<int>> multiply(vector<vector<int>> &A, vector<vector<int>> &B) {
        vector<pair<int, int>> locationA, locationB;
        // corner cases
        if (A.empty() || A.size() == 0 || A[0].size() == 0) return {};
        if (B.empty() || B.size() == 0 || B[0].size() == 0) return {};
        int rA = A.size(), cA = A[0].size();
        int rB = B.size(), cB = B[0].size();
        for (int i = 0; i < rA; i++) {
            for (int j = 0; j < cA; j++) {
                if (A[i][j]) locationA.push_back({i, j});
            }
        }
        for (int i = 0; i < rB; i++) {
            for (int j = 0; j < cB; j++) {
                if (B[i][j]) locationB.push_back({i, j});
            }
        }
        vector<vector<int>> ans(rA, vector<int>(cB));
        for (int i = 0; i < locationA.size(); i++) {
            pair<int, int> a = locationA[i];
            for (int j = 0; j < locationB.size(); j++) {
                pair<int, int> b = locationB[j];
                if (a.second == b.first) ans[a.first][b.second] += A[a.first][a.second] * B[b.first][b.second];
            }
        }
        return ans;
    }
};

tags: other

​