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.

Multiply Two Sparse Integer Matrices

Hints

1. Entry (i, j) only changes when both mat1[i][t] and mat2[t][j] are nonzero for some t. How can you skip the terms where either factor is zero?
2. Instead of computing each output entry as a dot product, try iterating over the nonzero entries of row i of mat1 and adding a scaled copy of row t of mat2 into output row i.
3. Preprocess mat2 once so that each of its rows is a short list of (column, value) pairs for the nonzero entries only.

Approach

The product entry result[i][j] is the sum of mat1[i][t] * mat2[t][j] over t. Rearranging the loops, output row i equals the sum over t of mat1[i][t] times row t of mat2. The reference first compresses every row of mat2 into a list of its nonzero (column, value) pairs. Then, for each row i of mat1, it starts from an all-zero row of length n, skips every t with mat1[i][t] == 0, and for each nonzero mat1[i][t] adds mat1[i][t] * value into column column for each stored pair of row t. Terms with a zero factor contribute nothing, so skipping them never changes a sum, and every nonzero term is added exactly once, so the result is exact even for dense inputs. Zero rows and cancelled entries remain as 0 because every output row is allocated in full. The inputs are only read, never written.

• Time complexity: O(k * n + m * k + Z), where Z is the number of pairs (mat1[i][t], mat2[t][j]) that are both nonzero; O(m * k * n) in the dense worst case
• Space complexity: O(m * n + nnz(mat2)) for the output and the compressed rows of mat2