Problem Statement
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.
Solution Explanation
A sparse matrix is a matrix or a 2D array in which majority of the elements are zero. Matrix multiplication is a very simple and straightforward operation and one, every computer science student encounters in the school at least once.
In a naive way, you multiply a values at row 'i' in matrix A with a column in the matrix B and store the sum of the row operation as a result in the resultant matrix.
However, since this problem involves sparse matrices, we can ignore the multiplication with the column in matrix B if the value iin matrix A is 0. This small optimization helps us in avoiding k operations where K is the number of rows in the matrix B.
For example, consider the below matrices
Matrix A
[
[ 2, 0, 0],
[-3, 0, 4]
]
Matrix B
[
[ 5, 0, 0 ],
[ 0, 6, 0 ],
[ 0, 0, 2 ]
]
In matrix A, the value at 0,1 and 0,2 are 0, hence we can skip the calculation to multiply with a column in the second matrix.
Here's the final solution in Java,
/*
Author : Venkatesh, Thallam
Date : 10/07/2017
*/
public class SparseMatrixMultiplication {
public static void main(String[] args) {
int[][] A = { { 2, 0, 0 }, { -3, 0, 4 } };
int[][] B = { { 5, 0, 0 }, { 0, 6, 0 }, { 0, 0, 2 } };
int[][] result = multiply(A, B);
for (int i = 0; i < result.length; i++) {
for (int j = 0; j < result[0].length; j++) {
System.out.print(" " + result[i][j]);
}
System.out.println();
}
}
public static int[][] multiply(int[][] A, int[][] B) {
int[][] result = new int[A.length][B[0].length];
int x = A.length, y = A[0].length, z = B[0].length;
for (int i = 0; i < x; i++) {
for (int j = 0; j < y; j++) {
if (A[i][j] != 0) {
for (int k = 0; k < z; k++) {
result[i][j] += A[i][j] * B[j][k];
}
}
}
}
return result;
}
}
Time Complexity
In the worst case when the matrix is not a sparse matrix, the time complexity would be O(m^2*n), where 'm' is the length of the first array and 'n' is the length of the second array and with the optimization, we can reduce it by a constant K where K is the no of zero's in the matrix A.