Multiply Two Sparse Integer Matrices Given as Dense Grids
Company: Netflix
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Online Assessment
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
```python
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`.
Overview: Given two integer matrices stored as dense lists of rows in which most entries are zero, return their exact matrix product. It tests handling matrix dimensions correctly and exploiting sparsity to skip work on zero entries while still producing every entry of the result.