Compress and Transpose a Sparse Matrix
Amazon● MediumFULLTIMEPHONE SCREENProblem statement
A sparse matrix has many zero entries. Given a rectangular integer matrix matrix, build a space-efficient representation of its nonzero entries and return the transpose in coordinate form.
Represent each nonzero entry of the transpose as [row, column, value]. Return the triples sorted first by transposed row, then by transposed column. Do not include zero entries. The transposed matrix has matrix[0].length rows and matrix.length columns. If every entry is zero, return an empty array.
For example, the value at original coordinate (r, c) becomes the same value at transposed coordinate (c, r). Your returned representation should use space proportional to the nonzero entries and matrix dimensions, instead of building a dense transposed matrix.
Function
transposeSparseMatrix(matrix: int[][]) → int[][]Examples
Example 1
matrix = [[0,5,0],[2,0,3]]return = [[0,1,2],[1,0,5],[2,1,3]]The three nonzero entries move from (0,1), (1,0), and (1,2) to (1,0), (0,1), and (2,1), respectively. The output lists them in transposed row-major order.
Example 2
matrix = [[0,0],[0,0]]return = []There are no nonzero entries to store.
Example 3
matrix = [[7,-1,0]]return = [[0,0,7],[1,0,-1]]The single input row becomes one column of the transpose. The negative value is retained, while the zero is omitted.
Constraints
1 <= matrix.length <= 200.1 <= matrix[0].length <= 200.- Every row has the same number of columns.
- Each entry is a signed 32-bit integer.