Sparse Matrix Multiplication in COO Form
Meta● MediumNEW GRADPHONE SCREENProblem statement
Matrix A has shape rowsA x shared and matrix B has shape shared x colsB. Each operand is given in coordinate-list (COO) form: every row [r,c,value] stores one nonzero integer at that zero-based coordinate. Coordinates are unique within each operand; missing cells equal zero.
Return the ordinary matrix product A times B in the same COO form. Omit zero output cells, including cells whose nonzero contributions cancel. Sort the output rows by coordinate, first row then column. Inputs need not be sorted.
Function
multiplySparseCOO(rowsA: int, shared: int, colsB: int, a: int[][], b: int[][]) → int[][]Examples
Example 1
rowsA = 2shared = 3colsB = 2a = [[0,0,2],[0,2,3],[1,1,-1]]b = [[0,1,4],[2,0,5],[1,1,6]]return = [[0,0,15],[0,1,8],[1,1,-6]]Three matching inner coordinates contribute to three nonzero output cells.
Example 2
rowsA = 2shared = 3colsB = 2a = [[0,0,5]]b = [[1,1,7]]return = []No A column matches a B row, so the product is all zero.
Example 3
rowsA = 1shared = 2colsB = 1a = [[0,0,1],[0,1,1]]b = [[0,0,3],[1,0,-3]]return = []Two contributions cancel, and COO omits the zero result.
Constraints
1 <= rowsA, shared, colsB <= 50.0 <= a.length, b.length <= 200.- Each COO row has three integers with an in-range row and column, a nonzero value in
[-100, 100], and no duplicate coordinate in the same operand. - Every output value fits in a signed 32-bit integer.