Skip to content

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<vector<int>> multiply(vector<vector<int>>& mat1,
                               vector<vector<int>>& mat2) {
    const int m = mat1.size();
    const int n = mat2.size();
    const int l = mat2[0].size();
    vector<vector<int>> ans(m, vector<int>(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<vector<int>> multiply(vector<vector<int>>& mat1,
                               vector<vector<int>>& mat2) {
    const int m = mat1.size();
    const int n = mat2.size();
    const int l = mat2[0].size();
    vector<vector<int>> ans(m, vector<int>(l));
    vector<vector<int>> nonZeroColIndicesInMat2;

    for (int i = 0; i < n; ++i) {
      vector<int> 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<Integer>[] nonZeroColIndicesInMat2 = new List[n];

    for (int i = 0; i < n; ++i) {
      List<Integer> 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