FastPrepSparse Matrix Multiplication

Sparse Matrix Multiplication

ByteDance logoByteDance● MediumFULLTIMEPHONE SCREEN

Problem statement

You are given two sparse matrices: mat1 with m rows and k columns, and mat2 with k rows and n columns. Most of their entries are usually zero.

Return the matrix product mat1 × mat2. It has m rows and n columns, and each entry is:

result[i][j] = mat1[i][0] * mat2[0][j] + mat1[i][1] * mat2[1][j] + ... + mat1[i][k - 1] * mat2[k - 1][j]

Return every entry of the result, including zeros. Try to skip work for zero entries instead of always doing all m * k * n multiplications.

Function

multiply(mat1: int[][], mat2: int[][]) → int[][]

Examples

Example 1

mat1 = [[1,0,0],[-1,0,3]]mat2 = [[7,0,0],[0,0,0],[0,0,1]]return = [[7,0,0],[-7,0,3]]

Row 0 of mat1 has one nonzero entry, 1 in column 0, so result row 0 is 1 times row 0 of mat2: [7,0,0].

Row 1 has -1 in column 0 and 3 in column 2. That gives -1 * [7,0,0] + 3 * [0,0,1] = [-7,0,3].

Example 2

mat1 = [[0]]mat2 = [[0]]return = [[0]]

The only product is 0 * 0 = 0.

Example 3

mat1 = [[0,2],[0,0],[1,0]]mat2 = [[0,0,4,0],[5,0,0,-1]]return = [[10,0,0,-2],[0,0,0,0],[0,0,4,0]]

The result has 3 rows and 4 columns.

  • Row 0 of mat1 only has 2 in column 1, so it is 2 * [5,0,0,-1] = [10,0,0,-2].
  • Row 1 is all zeros, so its result row is all zeros.
  • Row 2 only has 1 in column 0, so it is 1 * [0,0,4,0] = [0,0,4,0].

Constraints

  • 1 <= mat1.length <= 100
  • 1 <= mat2.length <= 100
  • Every row of mat1 has length mat2.length.
  • Every row of mat2 has the same length n, where 1 <= n <= 100.
  • -100 <= mat1[i][j], mat2[i][j] <= 100

More ByteDance problems

See ByteDance hiring insights
Saved
public int[][] multiply(int[][] mat1, int[][] mat2) {
    // Write your code here.
}
mat1[[1,0,0],[-1,0,3]]
mat2[[7,0,0],[0,0,0],[0,0,1]]
expected[[7,0,0],[-7,0,3]]
Checking account…