Sparse Matrix Multiplication from Coordinate Lists
Company: ByteDance
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
Implement sparse matrix multiplication from scratch. Matrix `A` has `n` rows and `m` columns, matrix `B` has `m` rows and `p` columns, and most entries of both are zero, so each matrix is given only by its nonzero entries, as `[row, column, value]` triples. Return the nonzero entries of the product `C = A · B` in the same format.
### Function Signature
```python
def multiply_sparse(n: int, m: int, p: int, a: list[list[int]], b: list[list[int]]) -> list[list[int]]:
```
### Rules
- Indices are 0-based. Every triple `[i, k, x]` in `a` means `A[i][k] = x`, with `0 <= i < n` and `0 <= k < m`. Every triple `[k, j, y]` in `b` means `B[k][j] = y`, with `0 <= k < m` and `0 <= j < p`. Entries that are not listed are `0`.
- Each `(row, column)` pair appears at most once in `a` and at most once in `b`, every listed value is nonzero, and the triples are in no particular order.
- `C[i][j]` is the sum over `k` of `A[i][k] * B[k][j]`.
- Return `[i, j, C[i][j]]` for every cell with `C[i][j] != 0`, sorted by `i` ascending, then by `j` ascending. A cell whose terms cancel to `0` is omitted. Return `[]` if every entry of `C` is `0`.
### Constraints
- `1 <= n, m, p <= 10^5`
- `0 <= len(a), len(b) <= 10^5`
- `-100 <= value <= 100` and `value != 0` for every listed entry
- The number of index triples `(i, k, j)` with both `A[i][k] != 0` and `B[k][j] != 0` is at most `10^6`.
- Every entry of `C` has absolute value at most `10^9`, so all values fit in a 32-bit signed integer.
### Examples
**Example 1**
```text
Input: n = 2, m = 3, p = 2,
a = [[0, 2, 2], [1, 1, -1], [0, 0, 1]],
b = [[2, 0, 5], [0, 1, 4], [1, 1, 3]]
Output: [[0, 0, 10], [0, 1, 4], [1, 1, -3]]
```
As dense matrices, `A = [[1, 0, 2], [0, -1, 0]]` and `B = [[0, 4], [0, 3], [5, 0]]`, so `C = [[10, 4], [0, -3]]`. The zero at `C[1][0]` is not returned.
**Example 2**
```text
Input: n = 1, m = 2, p = 1,
a = [[0, 0, 2], [0, 1, 3]],
b = [[0, 0, 3], [1, 0, -2]]
Output: []
```
`C[0][0] = 2 * 3 + 3 * (-2) = 0`, so the product has no nonzero entries.
**Example 3**
```text
Input: n = 1, m = 1, p = 3,
a = [[0, 0, -2]],
b = [[0, 2, 4], [0, 0, 1]]
Output: [[0, 0, -2], [0, 2, -8]]
```
`C = [[-2, 0, -8]]`. The entries are returned in column order even though `b` lists column `2` first.
Overview: Implement multiplication of two sparse matrices given as lists of nonzero row, column and value triples, and return the nonzero entries of the product in sorted order. It tests sparse data representations, avoiding work on zero entries, handling terms that cancel out and producing deterministic output.