# Sparse Matrix Multiplication (Java)

Spread the love

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

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

### 1. Naive Method

We can implement Sum(A_ik * B_kj) -> C_ij as a naive solution.

```public int[][] multiply(int[][] A, int[][] B) {
//validity check

int[][] C = new int[A.length][B[0].length];

for(int i=0; i<C.length; i++){
for(int j=0; j<C[0].length; j++){
int sum=0;
for(int k=0; k<A[0].length; k++){
sum += A[i][k]*B[k][j];
}
C[i][j] = sum;
}
}

return C;
}
```

Time complexity is O(n^3).

### 2. Optimized Method

From the formula: Sum(A_ik * B_kj) -> C_ij

We can see that when A_ik is 0, there is no need to compute B_kj. So we switch the inner two loops and add a 0-checking condition.

```public int[][] multiply(int[][] A, int[][] B) {
//validity check

int[][] C = new int[A.length][B[0].length];

for(int i=0; i<C.length; i++){
for(int k=0; k<A[0].length; k++){
if(A[i][k]!=0){
for(int j=0; j<C[0].length; j++){
C[i][j] += A[i][k]*B[k][j];
}
}
}
}

return C;
}
```

Since the matrix is sparse, the time complexity is ~O(n^2) which is much faster than O(n^3).