Sparse Matrix Multiplication 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 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

Implementation:-

class Solution {
   public int[][] multiply(int[][] mat1, int[][] mat2) {
      int n = mat1.length;
      int k = mat1[0].length;
      int m = mat2[0].length;

      // Product matrix will have 'n x m' size.
      int[][] ans = new int[n][m];
      for (int rowIndex = 0; rowIndex < n; ++rowIndex) {
            for (int elementIndex = 0; elementIndex < k; ++elementIndex) {
               // If current element of mat1 is non-zero then iterate over all columns of mat2.
               if (mat1[rowIndex][elementIndex] != 0)  {
                  for (int colIndex = 0; colIndex < m; ++colIndex) {
                        ans[rowIndex][colIndex] += mat1[rowIndex][elementIndex] * mat2[elementIndex][colIndex];
                  }
               }
            }
      }
      return ans;
   }
}
                 
                

Complexity Analysis

Likewise, let k and n represent the number of rows and columns in 2mat2, respectively.

Time complexity: O(m⋅k⋅n).

We iterate over all m⋅k elements of the matrix 1mat1.

For each element of matrix 1mat1, we iterate over all n columns of the matrix 2mat2.

Thus, it leads to a time complexity of m⋅k⋅n.

Space complexity: O(1).

We use a matrix ans of size m×n to output the multiplication result which is not included in auxiliary space