OA: Sparse Matrix Operation

Recommendation systems juggle huge user-by-item matrices in which almost every entry is 0. Build a class SparseMatrix that stores only the non-zero entries, so its memory grows with the number of non-zeros, never with rows * cols.

• SparseMatrix(rows: int, cols: int): an all-zero matrix (rows, cols >= 1; they may be as large as 10**9).
• shape() -> tuple[int, int]: (rows, cols).
• get(r, c) -> int and set(r, c, value) -> None: read or write one entry. Setting an entry to 0 must forget it. An index outside the matrix raises IndexError.
• nnz() -> int: how many entries are stored. Because zeros are never stored, this equals the number of non-zero entries.
• from_dense(grid: list[list[int]]) (a @classmethod): build from a non-empty rectangular list of lists.
• to_dense() -> list[list[int]]: the full matrix as lists (only called on small matrices).
• add(other) -> SparseMatrix: a new matrix with the element-wise sum; neither input changes. Shapes must match, otherwise raise ValueError. Entries that cancel to 0 must not be stored.

a = SparseMatrix.from_dense([[1, 0, 0],
                             [0, 0, 3]])
b = SparseMatrix(2, 3)
b.set(1, 2, -3)
b.set(0, 1, 4)
s = a.add(b)
s.to_dense()   # [[1, 4, 0], [0, 0, 0]]
s.nnz()        # 2      (the 3 + -3 cancelled)
a.get(1, 2)    # 3      (a is unchanged)
a.set(0, 0, 0)
a.nnz()        # 1
a.get(5, 0)    # IndexError

add must cost O(nnz(a) + nnz(b)), independent of the matrix dimensions.