FastPrep
Problem · Array

Sparse Matrix Multiplication

Learn this problem
● MediumApple logoAppleFULLTIMEPHONE SCREEN

Problem statement

You are given two rectangular integer matrices, mat1 with dimensions m × k and mat2 with dimensions k × n.

Return their matrix product product, an m × n matrix. For every valid row i and column j:

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

Sparse-matrix requirement

Many entries may be 0. Although the matrices use ordinary dense arrays for input and output, design the multiplication so it skips contributions whose left or right factor is 0.

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

The first row has only one nonzero value, so it contributes 1 × [7,0,0]. The second row contributes -1 × [7,0,0] and 3 × [0,0,1], producing [-7,0,3].

Example 2

mat1 = [[0,0],[0,0]]mat2 = [[1,2],[3,4]]return = [[0,0],[0,0]]

Every value in mat1 is 0, so there are no nonzero contributions to the product.

Example 3

mat1 = [[1,2],[0,3]]mat2 = [[4,0,5],[6,7,0]]return = [[16,14,5],[18,21,0]]

For example, product[0][0] = 1 × 4 + 2 × 6 = 16, while product[1][2] = 0 × 5 + 3 × 0 = 0.

Constraints

  • 1 ≤ m, k, n ≤ 100.
  • mat1.length = m and every row of mat1 has length k.
  • mat2.length = k and every row of mat2 has length n.
  • -100 ≤ mat1[i][t], mat2[t][j] ≤ 100.
  • The product of the two matrices fits in a signed 32-bit integer matrix.

More Apple problems

drafts saved locally
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