LC: 311. Sparse Matrix Multiplication - spiralgo/algorithms GitHub Wiki

311. Sparse Matrix Multiplication:

The Essence:

As many elements of the amtrix are 0, many elements of the resulting matrix will be too. Instead of trying to multiply all elements of the matrices, we can compress two matrices into a data structure that only contains elements at some index and row that contain non-zero values.

Details:

The easiest way of implementing such data structure is through a hash map of lists or hash maps, showing row-(column-value) pairs. It can also be implemented using list of lists or array of arrays.