Matrix Multiplication
Ninja has been given two sparse matrices ‘MAT1’ and ‘MAT2’ of integers having size ‘N’ x ‘M’ and ‘M’ x ‘P’, respectively.

A sparse matrix is a matrix that contains very few non-zero elements.

Ninja has to find the matrix formed by the multiplication of ‘MAT1’ and ‘MAT2’. As Ninja is busy with some other tasks so he needs your help. Can you help Ninja to find the matrix formed by the multiplication of ‘MAT1’ and ‘MAT2’?

Note: The number of columns in ‘MAT1’ i.e ‘M’ is equal to the number of rows in ‘MAT2’ i.e ‘M’. It means we can always multiply ‘MAT1’ with ‘MAT2’.

For example:

For the ‘MAT1’ and ‘MAT2’ given below, ‘MAT3’ is the matrix formed by multiplying ‘MAT1’ and ‘MAT2’.

1. MAT3[0][0] = MAT1[0][0] * MAT2[0][0] + MAT1[0][1] * MAT2[1][0] ie. 2 * 1 + 1 * 4 = 6 2. MAT3[1][0] = MAT1[1][0] * MAT2[1][0] + MAT1[1][1] * MAT2[1][0] ie. 0 * 6 + 0 * 4 = 0

Input Format:

The first line of input contains an integer ‘T’ denoting the number of test cases. Then each test case follows. The first line of each test case contains four space-separated integers ‘N’, ‘M’, ‘M’, ‘P’ where ‘N’ and ‘M’ representing the number of rows and columns of ‘MAT1’ respectively and ‘M’ and ‘P’ representing the number of rows and columns of ‘MAT2’ respectively. The next ‘N’ lines of each test case contain ‘M’ single space-separated integers denoting the values of ‘MAT1’. Then the next ‘M’ lines contain ‘P’ single space-separated integers denoting the values of ‘MAT2’

Output Format :

For each test case, return the matrix ‘MAT3’ which will be formed by multiplying ‘MAT1’ and ‘MAT2’.

Note:

You are not required to print the expected output; it has already been taken care of. Just implement the function.

Constraints:

1

Question

Matrix Multiplication

Ninja has been given two sparse matrices ‘MAT1’ and ‘MAT2’ of integers having size ‘N’ x ‘M’ and ‘M’ x ‘P’, respectively.

A sparse matrix is a matrix that contains very few non-zero elements.

Ninja has to find the matrix formed by the multiplication of ‘MAT1’ and ‘MAT2’. As Ninja is busy with some other tasks so he needs your help. Can you help Ninja to find the matrix formed by the multiplication of ‘MAT1’ and ‘MAT2’?

Note: The number of columns in ‘MAT1’ i.e ‘M’ is equal to the number of rows in ‘MAT2’ i.e ‘M’. It means we can always multiply ‘MAT1’ with ‘MAT2’.

For example:

For the ‘MAT1’ and ‘MAT2’ given below, ‘MAT3’ is the matrix formed by multiplying ‘MAT1’ and ‘MAT2’.

1. MAT3[0][0] = MAT1[0][0] * MAT2[0][0] + MAT1[0][1] * MAT2[1][0]  ie. 2 * 1 + 1 * 4 = 6
2. MAT3[1][0] = MAT1[1][0] * MAT2[1][0] + MAT1[1][1] * MAT2[1][0] ie. 0 * 6 + 0 * 4 = 0

Input Format:

The first line of input contains an integer ‘T’ denoting the number of test cases. Then each test case follows.

The first line of each test case contains four space-separated integers ‘N’, ‘M’, ‘M’, ‘P’ where ‘N’ and ‘M’ representing the number of rows and columns of ‘MAT1’ respectively and ‘M’ and ‘P’ representing the number of rows and columns of ‘MAT2’ respectively. 

The next ‘N’ lines of each test case contain ‘M’ single space-separated integers denoting the values of ‘MAT1’. Then the next ‘M’ lines contain ‘P’ single space-separated integers denoting the values of ‘MAT2’

Output Format :

For each test case, return the matrix ‘MAT3’ which will be formed by multiplying ‘MAT1’ and ‘MAT2’.

Note:

You are not required to print the expected output; it has already been taken care of. Just implement the function.

Constraints:

1 <= ‘T’ <= 100
1 <= ‘N’, ‘M’ and ‘P’ <= 100
-10^5 <= ‘MAT1[i][j]’ and ‘MAT2[i][j]’ <= 10^5

Time limit: 1 sec

Accepted Answer

Brute Force

We can get the matrix ‘MAT3’ using 3 nested loops.
To get the (‘i’, ‘j’) cell element of the matrix ‘MAT3’, we need to multiply each element of the ‘i’th row of ‘MAT1’ with the ‘j’’th column of the matrix ‘MAT2’ and finally add all the results.

Here is the complete algorithm:

Make a 2D array/list ‘MAT3’ having ‘N’ rows and ‘P’ columns.
Run a for loop from ‘i’ = 0 to ‘i’ < ‘N’ and for each ‘i’ do the following:
- Run a for loop from ‘j’ = 0 to ‘j’ < ‘P’ and for each ‘j’ do the following:
  - Make a variable ‘sum’ = 0.
  - Run a for loop from ‘k’ = 0 to ‘k’ < ‘M’ and for each ‘k’ do the following:
    - ‘sum’ = ‘sum’ + ‘MAT1[i][k]’ * ‘MAT2[k][j]’.
  - Update ‘MAT3[i][j]’ = ‘sum’.
Return ‘MAT3’.

Space Complexity: O(1)Explanation:

O(1).

Because we are not using any extra space for finding our resultant answer.

Time Complexity: OtherExplanation:

O(N * M * P), where ‘N’ and ‘M’ denote the number of rows and columns of the matrix ‘MAT1’ and ‘P’ denotes the number of columns in ‘MAT2’.

We are using 3 nested loops. Hence, the overall time complexity is O(N * M * P).

Python (3.5)

'''

    Time Complexity : O(N * M * P)

    Space Complexity : O(1)



    where 'N' and 'M' denote the number of rows and columns of the matrix 'MAT1'

    and 'P' denote the number of columns in 'MAT2'.

'''



def multiplyMatrices(mat1, mat2):

    n = len(mat1)

    m = len(mat1[0])    

    p = len(mat2[0])



    # Resultant matrix to store product of the mat1 and mat2. 

    mat3 = [[0 for j in range(p)] for i in range(n)]



    # Mutliplying mat1 and mat2 and storing result in mat3.

    for i in range(n):

        for j in range(p):

            sum = 0

            for k in range(m):

                sum = sum + mat1[i][k] * mat2[k][j]

            

            mat3[i][j] = sum



    return mat3

Java (SE 1.8)

/*
    Time Complexity : O(N * M * P)
    Space Complexity : O(1)

    where 'N' and 'M' denote the number of rows and columns of the matrix 'MAT1'
    and 'P' denote the number of columns in 'MAT2'.
*/

import java.util.ArrayList;

public class Solution {
    public static ArrayList> multiplyMatrices(ArrayList> mat1, ArrayList> mat2) {
        int n = mat1.size();
        int m = mat1.get(0).size();
        int p = mat2.get(0).size();

        // Resultant matrix to store product of the mat1 and mat2. 
        int[][] mat3 = new int[n][p];

        // Mutliplying mat1 and mat2 and storing result in mat3.
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < p; ++j) {
                int sum = 0;
                for (int k = 0; k < m; ++k) {
                    sum = sum + mat1.get(i).get(k) * mat2.get(k).get(j);
                }

                mat3[i][j] = sum;
            }
        }

        ArrayList> pro = new ArrayList>();
        for(int i = 0; i < n; i++){
            ArrayList temp = new ArrayList<>();
            for(int j = 0; j < p; j++){
                temp.add(mat3[i][j]);
            }
            pro.add(temp);
        }

        return pro;
    }
}

C++ (g++ 5.4)

/*
    Time Complexity : O(N * M * P)
    Space Complexity : O(1)

    where ‘N’ and ‘M’ denote the number of rows and columns of the matrix ‘MAT1’
    and ‘P’ denote the number of columns in ‘MAT2’.
*/

vector> multiplyMatrices(vector> &mat1,
                                     vector> &mat2) {
    int n = mat1.size();
    int m = mat1[0].size();
    int p = mat2[0].size();

    // Resultant matrix to store product of the mat1 and mat2. 
    vector> mat3(n, vector(p, 0));

    // Mutliplying mat1 and mat2 and storing result in mat3.
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < p; ++j) {
            int sum = 0;
            for (int k = 0; k < m; ++k) {
                sum = sum + mat1[i][k] * mat2[k][j];
            }

            mat3[i][j] = sum;
        }
    }

    return mat3;
}

Accepted Answer

Brute Force with Optimization

We can optimize the above approach because in ‘MAT1’ and ‘MAT2’ we have more zero elements than non-zero as both the matrices are sparse matrices.
From the formula: Sum(MAT1_ik * MAT2_kj) -> MAT3_ij, we can see that when ‘MAT1_ik’ is 0, there is no need to compute ‘MAT2_kj’. So we switch the inner two loops and add a 0-checking condition.

Here is the complete Algorithm:

Make a 2D array ‘C’ having ‘N’ rows and ‘P’ columns.
Run a for loop from ‘i’ = 0 to ‘i’ < ‘N’ and for each ‘i’ do the following:
- Run a for loop from ‘k’ = 0 to ‘k’ < ‘M’ and for each ‘j’ do the following:
  - If ‘MAT1[i][k]’ is not 0 then do the following:
    - Run a for loop from ‘j’ = 0 to ‘j’ < ‘P’ and for each ‘j’ do the following:
      - ‘MAT3[i][j]’ = ‘MAT3[i][j]’ + ‘MAT1[i][k]’ * ‘MAT2[k][j]’
Return ‘MAT3’.

Space Complexity: O(1)Explanation:

O(1).

Because we are not using any extra space for finding our resultant answer.

Time Complexity: O(1)Explanation:

O(N * M), where ‘N’ and ‘M’ denote the number of rows and columns of the matrix ‘MAT1’.

We are using 3 nested loops but since both matrices are sparse matrices i.e have more 0s than non-zero elements, the number of times the inner loop will be executed will be very low than ‘P’. Hence, the overall time complexity is O(N * M).