Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/311.html

Given two sparse matrices mat1 of size m x k and mat2 of size k x n, return the result of mat1 x mat2. You may assume that multiplication is always possible.

 

Example 1:

Input: mat1 = [[1,0,0],[-1,0,3]], mat2 = [[7,0,0],[0,0,0],[0,0,1]]
Output: [[7,0,0],[-7,0,3]]

Example 2:

Input: mat1 = [[0]], mat2 = [[0]]
Output: [[0]]

 

Constraints:

• m == mat1.length
• k == mat1[i].length == mat2.length
• n == mat2[i].length
• 1 <= m, n, k <= 100
• -100 <= mat1[i][j], mat2[i][j] <= 100

Algorithm

Make sure that A[i][k] is not 0 before continuing to calculate, and then traverse the kth row of matrix B. If B[K][J] is not 0, accumulate the result matrix res[i][j] += A[i][k] * B[k][j], so that we can efficiently calculate the multiplication of the sparse matrix.

Code

• Java
• C++
• Python
• Go

• 
  public class Sparse_Matrix_Multiplication {
  
      public int[][] multiply(int[][] A, int[][] B) {
  
          //validity check
          int[][] C = new int[A.length][B[0].length];
  
          for (int i = 0; i < C.length; i++) {
              for (int k = 0; k < A[0].length; k++) {
                  if (A[i][k] != 0) { // @note: non-zero check. if zero, then skip since result will be 0
                      for (int j = 0; j < C[0].length; j++) {
                          C[i][j] += A[i][k] * B[k][j];
                      }
                  }
              }
          }
  
          return C;
      }
  }
  
  ############
  
  class Solution {
      public int[][] multiply(int[][] mat1, int[][] mat2) {
          int r1 = mat1.length, c1 = mat1[0].length, c2 = mat2[0].length;
          int[][] res = new int[r1][c2];
          Map<Integer, List<Integer>> mp = new HashMap<>();
          for (int i = 0; i < r1; ++i) {
              for (int j = 0; j < c1; ++j) {
                  if (mat1[i][j] != 0) {
                      mp.computeIfAbsent(i, k -> new ArrayList<>()).add(j);
                  }
              }
          }
          for (int i = 0; i < r1; ++i) {
              for (int j = 0; j < c2; ++j) {
                  if (mp.containsKey(i)) {
                      for (int k : mp.get(i)) {
                          res[i][j] += mat1[i][k] * mat2[k][j];
                      }
                  }
              }
          }
          return res;
      }
  }
  

• // OJ: https://leetcode.com/problems/sparse-matrix-multiplication/
  // Time: O(MNK)
  // Space: O(1)
  class Solution {
  public:
      vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
          int M = A.size(), K = A[0].size(), N = B[0].size();
          vector<vector<int>> ans(M, vector<int>(N));
          for (int i = 0; i < M; ++i) {
              for (int j = 0; j < N; ++j) {
                  for (int k = 0; k < K; ++k) {
                      ans[i][j] += A[i][k] * B[k][j];
                  }
              }
          }
          return ans;
      }
  };
  

• class Solution:
      def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:
          r1, c1, c2 = len(mat1), len(mat1[0]), len(mat2[0])
          res = [[0] * c2 for _ in range(r1)]
          mp = defaultdict(list)
          for i in range(r1):
              for j in range(c1):
                  if mat1[i][j] != 0:
                      mp[i].append(j)
          for i in range(r1):
              for j in range(c2):
                  for k in mp[i]:
                      res[i][j] += mat1[i][k] * mat2[k][j]
          return res
  
  ############
  
  class Solution(object):
    def multiply(self, A, B):
      """
      :type A: List[List[int]]
      :type B: List[List[int]]
      :rtype: List[List[int]]
      """
      ret = [[0 for j in range(len(B[0]))] for i in range(len(A))]
  
      for i, row in enumerate(A):
        for k, a in enumerate(row):
          if a:
            for j, b in enumerate(B[k]):
              if b:
                ret[i][j] += a * b
      return ret
  
  

• func multiply(mat1 [][]int, mat2 [][]int) [][]int {
  	r1, c1, c2 := len(mat1), len(mat1[0]), len(mat2[0])
  	res := make([][]int, r1)
  	for i := range res {
  		res[i] = make([]int, c2)
  	}
  	mp := make(map[int][]int)
  	for i := 0; i < r1; i++ {
  		for j := 0; j < c1; j++ {
  			if mat1[i][j] != 0 {
  				mp[i] = append(mp[i], j)
  			}
  		}
  	}
  	for i := 0; i < r1; i++ {
  		for j := 0; j < c2; j++ {
  			for _, k := range mp[i] {
  				res[i][j] += mat1[i][k] * mat2[k][j]
  			}
  		}
  	}
  	return res
  }
  

All Problems

All Solutions