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.

SparseMatMul.java

/*
a[2][3]
1 2 3 
4 5 6

b[3][2]
7  8
9  10
11 12

c[2][2]
1*7+2*9+3*11=58  1*8+2*10+3*12=64
4*7+5*9+6*11=139 4*8+5*10+6*12=154

i	j	k	c
0	0	0	c[0, 0] += 1*7
0	1	0	c[0, 1] += 1*8
0	0	1	c[0, 0] += 2*9
0	1	1	c[0, 1] += 2*10
0	0	2	c[0, 0] += 3*11
0	1	2	c[0, 1] += 3*12
1	0	0	c[1, 0] += 4*7
1	1	0	c[1, 1] += 4*8
1	0	1	c[1, 0] += 5*9
1	1	1	c[1, 1] += 5*10
1	0	2	c[1, 0] += 6*11
1	1	2	c[1, 1] += 6*12
*/
public int[][] multiply(int[][] a, int[][] b) {
	int mA = a.length, nA = a[0].length;
	int mB = b.length, nB = b[0].length;

	if(nA != mB) throw new IllegalArgumentException();
	int[][] C = new int[mA][nB];

	for(int i = 0; i < mA; i++) {
		for(int k = 0; k < nA; k++) {   // swapping j and k for loops
			if(a[i][k] == 0) continue;  // go down only if a[i][k] is non-zero
			for(int j = 0; j < nB; j++) {
				if(b[k][j] == 0) continue;
				c[i][j] += a[i][k] * b[k][j];
			}
		}
	}

	return c;
}