Multiply Two Sparse Integer Matrices Given as Dense Grids

You are given two integer matrices: mat1 with m rows and k columns, and mat2 with k rows and n columns. Each matrix is given as a list of rows, and most of their entries are zero.

Return their matrix product: the matrix with m rows and n columns whose entry in row i and column j is the sum, over every t from 0 to k - 1, of mat1[i][t] * mat2[t][j].

Function Signature

def multiply_sparse(mat1: list[list[int]], mat2: list[list[int]]) -> list[list[int]]:

Rules

• Return a new list of exactly m rows, each a list of exactly n integers. Rows and entries that are zero are included, not omitted.
• Do not modify mat1 or mat2.
• The inputs are expected to be sparse, but the result must be exact for every input that satisfies the constraints, including dense ones.

Constraints

• 1 <= m, k, n <= 300
• len(mat1) == m and every row of mat1 has length k.
• len(mat2) == k and every row of mat2 has length n.
• -100 <= mat1[i][t] <= 100 and -100 <= mat2[t][j] <= 100
• Every entry of the result has absolute value at most 300 * 100 * 100 = 3000000, which is well inside the 32-bit signed integer range.
• The result is uniquely determined by the input.

Examples

Example 1

• Input: mat1 = [[2, 0, 0], [0, 0, -3]], mat2 = [[0, 4], [5, 0], [0, 1]]
• Output: [[0, 8], [0, -3]]
• Explanation: Entry (0, 1) is 2 * 4 + 0 * 0 + 0 * 1 = 8, and entry (1, 1) is 0 * 4 + 0 * 0 + (-3) * 1 = -3. Entries (0, 0) and (1, 0) are 2 * 0 + 0 * 5 + 0 * 0 = 0 and 0 * 0 + 0 * 5 + (-3) * 0 = 0.

Example 2

• Input: mat1 = [[0, 0], [0, 0]], mat2 = [[0, 0, 7], [1, 0, 0]]
• Output: [[0, 0, 0], [0, 0, 0]]
• Explanation: The first matrix is all zeros, so the product is the all-zero matrix with 2 rows and 3 columns.

Example 3

• Input: mat1 = [[1, -1, 0, 0]], mat2 = [[2], [2], [0], [9]]
• Output: [[0]]
• Explanation: 1 * 2 + (-1) * 2 + 0 * 0 + 0 * 9 = 0. Nonzero terms can cancel, and the entry is still reported as 0.