Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

311. Sparse Matrix Multiplication

Time: $O(mnl)$

Space: $O(nl)$

			


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;
  }
};




			


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;
  }
}




			


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