# 311. Sparse Matrix Multiplication¶

## Approach 1: Brute Force¶

• Time: $O(mnl)$
• Space: $O(nl)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public: vector> multiply(vector>& mat1, vector>& mat2) { const int m = mat1.size(); const int n = mat2.size(); const int l = mat2[0].size(); vector> ans(m, vector(l)); for (int i = 0; i < m; ++i) for (int j = 0; j < l; ++j) for (int k = 0; k < n; ++k) ans[i][j] += mat1[i][k] * mat2[k][j]; return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution { public int[][] multiply(int[][] mat1, int[][] mat2) { final int m = mat1.length; final int n = mat2.length; final int l = mat2[0].length; int[][] ans = new int[m][l]; for (int i = 0; i < m; ++i) for (int j = 0; j < l; ++j) for (int k = 0; k < n; ++k) ans[i][j] += mat1[i][k] * mat2[k][j]; return ans; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution: def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]: m = len(mat1) n = len(mat2) l = len(mat2[0]) ans = [[0] * l for _ in range(m)] for i in range(m): for j in range(l): for k in range(n): ans[i][j] += mat1[i][k] * mat2[k][j] return ans 

## Approach 2: Look up¶

• Time: $O(nl + mn \times \text{nonZero}(B))$
• Space: $O(ml + \text{nonZero}(B))$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution { public: vector> multiply(vector>& mat1, vector>& mat2) { const int m = mat1.size(); const int n = mat2.size(); const int l = mat2[0].size(); vector> ans(m, vector(l)); vector> nonZeroColIndicesInMat2; for (int i = 0; i < n; ++i) { vector colIndices; for (int j = 0; j < l; ++j) if (mat2[i][j] != 0) colIndices.push_back(j); nonZeroColIndicesInMat2.push_back(colIndices); } for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) { if (mat1[i][j] == 0) continue; // mat1's j-th column matches mat2's j-th row for (const int colIndex : nonZeroColIndicesInMat2[j]) ans[i][colIndex] += mat1[i][j] * mat2[j][colIndex]; } return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 class Solution { public int[][] multiply(int[][] mat1, int[][] mat2) { final int m = mat1.length; final int n = mat2.length; final int l = mat2[0].length; int[][] ans = new int[m][l]; List[] nonZeroColIndicesInMat2 = new List[n]; for (int i = 0; i < n; ++i) { List colIndices = new ArrayList<>(); for (int j = 0; j < l; ++j) if (mat2[i][j] != 0) colIndices.add(j); nonZeroColIndicesInMat2[i] = colIndices; } for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) { if (mat1[i][j] == 0) continue; // mat1s j-th column matches mat2's j-th row for (final int colIndex : nonZeroColIndicesInMat2[j]) ans[i][colIndex] += mat1[i][j] * mat2[j][colIndex]; } return ans; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution: def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]: m = len(mat1) n = len(mat2) l = len(mat2[0]) ans = [[0] * l for _ in range(m)] nonZeroColIndicesInMat2 = [ [j for j, a in enumerate(row) if a] for row in mat2 ] for i in range(m): for j, a in enumerate(mat1[i]): if a == 0: continue # mat1s j-th column matches mat2's j-th row for colIndex in nonZeroColIndicesInMat2[j]: ans[i][colIndex] += a * mat2[j][colIndex] return ans