The challenge
Write a function that accepts two square (NxN) matrices (two dimensional arrays), and returns the product of the two. Only square matrices will be given.
How to multiply two square matrices:
We are given two matrices, A and B, of size 2×2 (note: tests are not limited to 2×2). Matrix C, the solution, will be equal to the product of A and B. To fill in cell [0][0] of matrix C, you need to compute: A[0][0] * B[0][0] + A[0][1] * B[1][0].
More general: To fill in cell [n][m] of matrix C, you need to first multiply the elements in the nth row of matrix A by the elements in the mth column of matrix B, then take the sum of all those products. This will give you the value for cell [m][n] in matrix C.
Example
A B C
|1 2| x |3 2| = | 5 4|
|3 2| |1 1| |11 8|
Detailed calculation:
C[0][0] = A[0][0] * B[0][0] + A[0][1] * B[1][0] = 1*3 + 2*1 = 5
C[0][1] = A[0][0] * B[0][1] + A[0][1] * B[1][1] = 1*2 + 2*1 = 4
C[1][0] = A[1][0] * B[0][0] + A[1][1] * B[1][0] = 3*3 + 2*1 = 11
C[1][1] = A[1][0] * B[0][1] + A[1][1] * B[1][1] = 3*2 + 2*1 = 8
Link to Wikipedia explaining matrix multiplication (look at the square matrix example): http://en.wikipedia.org/wiki/Matrix_multiplication
A more visual explanation of matrix multiplication: http://matrixmultiplication.xyz
The solution in Java code
Option 1:
public class Solution {
public static int[][] matrixMultiplication(int[][] a, int[][] b) {
int[][] resultMatrix = new int[a.length][b[0].length];
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < b[0].length; j++) {
for (int k = 0; k < b.length; k++) {
resultMatrix[i][j] += a[i][k] * b[k][j];
}
}
}
return resultMatrix;
}
}
Option 2:
public class Solution {
public static int[][] matrixMultiplication(int[][] a, int[][] b) {
int n = a.length;
int[][] res = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
res[i][j] += a[i][k] * b[k][j];
}
}
}
return res;
}
}
Option 3:
public class Solution {
public static int[][] matrixMultiplication(int[][] a, int[][] b) {
int n = a.length;
int[][] c = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int f = 0; f < n; f++) {
c[i][j] += a[i][f] * b[f][j];
}
}
}
return c;
}
}
Test cases to validate our solution
import java.util.Random;
import java.util.function.IntSupplier;
import org.junit.Assert;
import org.junit.Test;
public class SolutionTest {
@Test
public void exampleTest() {
int[][] a = {
{1,2},
{3, 2}};
int[][] b = {
{3,2},
{1, 1}};
int[][] expected = {
{5, 4},
{11, 8}};
int[][] actual = Solution.matrixMultiplication(a, b);
Assert.assertArrayEquals(expected, actual);
}
@Test
public void basicTest() {
{
int[][] a = {
{ 9, 7 },
{ 0, 1 }};
int[][] b = {
{ 1, 1 },
{ 4, 12 }};
int[][] expected = {
{ 37, 93 },
{ 4, 12 }};
int[][] actual = Solution.matrixMultiplication(a, b);
Assert.assertArrayEquals(expected, actual);
}
{
int[][] a = {
{ 1, 2, 3 },
{ 3, 2, 1 },
{ 2, 1, 3 }};
int[][] b = {
{ 4, 5, 6 },
{ 6, 5, 4 },
{ 4, 6, 5 }};
int[][] expected = {
{ 28, 33, 29 },
{ 28, 31, 31 },
{ 26, 33, 31 }};
int[][] actual = Solution.matrixMultiplication(a, b);
Assert.assertArrayEquals(expected, actual);
}
}
}
