## 311. Sparse Matrix Multiplication

Given twosparse matrices A and B, return the result of AB.

You may assume that A's column number is equal to B's row number.

Example:

``````Input:

A = [
[ 1, 0, 0],
[-1, 0, 3]
]

B = [
[ 7, 0, 0 ],
[ 0, 0, 0 ],
[ 0, 0, 1 ]
]

Output:

|  1 0 0 |   | 7 0 0 |   |  7 0 0 |
AB = | -1 0 3 | x | 0 0 0 | = | -7 0 3 |
| 0 0 1 |
``````

Thoughts:

1. Idea from a CMU lecture.: A sparse matrix can be represented as a sequence of rows, each of which is a sequence of (column-number, value) pairs of the nonzero values in the row.
2. Time Complexity Proposal: O(m*n + k*nB). Here k: number of non-empty elements in A. So in the worst case (dense matrix), it's O(m*n*nB)(from here)

Code:

``````class Solution {
public int[][] multiply(int[][] A, int[][] B) {
int m = A.length, n = A[0].length, nB = B[0].length;
int [][] res = new int [m][nB];
List[] rowA = new List[m];

for(int i = 0; i < m; i++){
List<Integer> colVal = new ArrayList<>();
for (int j = 0 ; j < n; j ++){
if(A[i][j]!= 0){
}
}
rowA[i] = colVal;
}

for(int i = 0; i < m; i++){
List<Integer> colVal = rowA[i];
for(int p = 0; p < colVal.size(); p+=2){
int colA = colVal.get(p);
int valA = colVal.get(p + 1);
for(int j = 0; j < nB; j++){
int valB = B[colA][j];
res[i][j] += valA * valB;
}
}
}

return res;
}
}
``````

Code: improvements: Definition of matrix multiplication: No extra space required

``````class Solution {
public int[][] multiply(int[][] A, int[][] B) {
int m = A.length, n = A[0].length, nB = B[0].length;

int[][] res = new int[m][nB];

for(int i = 0; i < m; i++){
for(int k = 0; k < n; k++){
if(A[i][k] != 0){
for(int j = 0; j < nB; j++){
if(B[k][j] != 0)
res[i][j] += A[i][k] * B[k][j];
}
}
}
}

return res;
}
}
``````