Sparse Matrix Addition and Multiplication
Problem statement
A sparse matrix is mostly zeros, so it is stored in coordinate form: a list of rows [row, col, value], one for each nonzero cell, with zero-based indices. Every cell that is not listed is 0. For example, the matrix [[0,3,0],[4,7,0],[0,0,0]] is stored as [[0,1,3],[1,0,4],[1,1,7]].
You are given two n x n matrices a and b in coordinate form, with their rows in any order, and a string operation:
"ADD": computea + b, adding the two values of each cell."MULTIPLY": compute the matrix producta * b. Cell(i, j)of the product is the sum ofa[i][k] * b[k][j]over everyk.
Return the result in the same coordinate form. List only the nonzero cells of the result: a cell whose contributions add up to 0 is left out. Sort the cells by row, and cells in the same row by column. If the result has no nonzero cell, return an empty list.
n can be as large as 10^9, so the matrices cannot be stored in full.
Function
sparseMatrixOperation(n: int, a: int[][], b: int[][], operation: String) → int[][]Examples
Example 1
n = 3a = [[0,1,3],[1,0,4],[1,1,7]]b = [[1,1,1],[0,1,-3],[2,2,5]]operation = "ADD"return = [[1,0,4],[1,1,8],[2,2,5]]Matrix a is [[0,3,0],[4,7,0],[0,0,0]] written as its three nonzero cells. Adding cell by cell: position (0,1) becomes 3 + (-3) = 0, so it is left out; (1,0) stays 4; (1,1) becomes 7 + 1 = 8; (2,2) comes only from b and stays 5. The cells are listed by row, then by column.
Example 2
n = 3a = [[0,1,3],[1,0,4],[1,1,7]]b = [[0,2,1],[1,2,5],[0,0,2]]operation = "MULTIPLY"return = [[0,2,15],[1,0,8],[1,2,39]]Row 0 of a has only 3 in column 1, so it picks up row 1 of b times 3: cell (0,2) is 3 * 5 = 15. Row 1 of a has 4 in column 0 and 7 in column 1. Cell (1,0) is 4 * 2 = 8, and cell (1,2) is 4 * 1 + 7 * 5 = 39.
Example 3
n = 1000000000a = [[999999999,7,2],[0,1,2],[0,2,1]]b = [[2,4,-6],[1,4,3],[7,0,5]]operation = "MULTIPLY"return = [[999999999,0,10]]The matrices are 10^9 x 10^9, far too large to store in full. Cell (999999999,0) is 2 * 5 = 10. Cell (0,4) gets 2 * 3 = 6 through index 1 and 1 * (-6) = -6 through index 2. These cancel to 0, so that cell is left out.
Constraints
1 <= n <= 10^90 <= a.length, b.length <= 1000a[i].length == b[j].length == 3- Each row
[row, col, value]has0 <= row, col < nand a nonzerovaluewith-1000 <= value <= 1000. - Within one matrix, no two rows have the same
(row, col)position. operationis either"ADD"or"MULTIPLY".