311. Sparse Matrix Multiplication

Problem Statement

link: LeetCode.cn LeetCode 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:

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]]

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

Solution Approach

The solution iterates through the non-zero elements of the first matrix and computes the product with corresponding elements in the second matrix, updating the result matrix accordingly.

Algorithm

1. Identify Non-Zero Elements: Traverse the rows of the first matrix to identify non-zero elements, which contribute to the final result.
2. Multiply and Accumulate: For each non-zero element in the first matrix, multiply it with the corresponding elements in the second matrix and add the result to the appropriate position in the result matrix.
3. Return the Result Matrix: After completing the multiplication and accumulation for all relevant elements, return the result matrix as the final output.

Implement

    class Solution:
  def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:
      ans = [[0] * len(mat2[0]) for _ in range(len(mat1))]
      for i, row in enumerate(mat1):
          for k, a in enumerate(row):
              if a:
                  for j, b in enumerate(mat2[k]):
                      ans[i][j] += a * b
      return ans 

    
    

Twitter  facebook  Email