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.
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 triple format.
Implement `multiply_sparse(n, m, p, a, b)`.
### 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 (no value exceeds `2^31 - 1`).
### 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 = 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.
Constraints
- 1 <= n, m, p <= 10^5
- 0 <= len(a), len(b) <= 10^5
- -100 <= value <= 100 and value != 0 for every listed entry
- 0 <= i < n, 0 <= k < m and 0 <= j < p for every listed triple; each (row, column) pair appears at most once in a and at most once in b
- 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 (no value exceeds 2^31 - 1)
Examples
Input: (2, 3, 2, [[0, 2, 2], [1, 1, -1], [0, 0, 1]], [[2, 0, 5], [0, 1, 4], [1, 1, 3]])
Expected Output: [[0, 0, 10], [0, 1, 4], [1, 1, -3]]
Explanation: Source example 1: C = [[10, 4], [0, -3]]; the zero at C[1][0] is not returned.
Input: (1, 2, 1, [[0, 0, 2], [0, 1, 3]], [[0, 0, 3], [1, 0, -2]])
Expected Output: []
Explanation: Source example 2: C[0][0] = 2*3 + 3*(-2) = 0, so the all-cancel product returns [].
Hints
- Only listed entries can contribute: the term A[i][k] * B[k][j] is nonzero only when an entry of a has column k and an entry of b has row k.
- The dimensions can reach 10^5, so a dense table of A, B or C is far too large; aim for work proportional to the number of contributing (i, k, j) triples.
- Several terms can land in the same cell and may cancel, even temporarily; decide whether a cell is reported only after all of its terms are added, and emit cells in (i, j) order.