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.