Mid/Senior
Sparse Matrix Multiplication
Given two sparse matrices mat1 of size m x k and mat2 of size k x n, return the result of multiplying mat1 and mat2.
Matrix multiplication produces a matrix answer of size m x n, where each answer[i][j] is the dot product of row i from mat1 and column j from mat2.
The matrices are sparse, meaning most of their elements are 0. Your solution should take advantage of sparsity when possible.
Example 1
1 0 0 -1 0 3 7 0 0 0 0 0 0 0 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]]The first row of the product is [7, 0, 0], and the second row is [-7, 0, 3].
Example 2
0 0
Input
mat1 = [[0]], mat2 = [[0]]Output
[[0]]Multiplying a 1x1 zero matrix by another 1x1 zero matrix results in a 1x1 zero matrix.
Constraints
- m == mat1.length
- k == mat1[i].length
- k == mat2.length
- n == mat2[i].length
- 1 <= m, n, k <= 100
- -100 <= mat1[i][j], mat2[i][j] <= 100