Sparse Matrix Multiplication - Leetcode Solution

Problem:

Given two sparse matrices A and B, return their product.

You may assume that A's column number is equal to B's row number.

Input: A = [ [ 1, 0, 0], [-1, 0, 3] ]

B = [ [ 7, 0, 0 ], [ 0, 0, 0 ], [ 0, 0, 1 ] ]

Output: | 1 0 0 | | 7 0 0 | | 7 0 0 | AB = | -1 0 3 | x | 0 0 0 | = | -7 0 3 | | 0 0 1 |

Solution:

Approach: The first intuition that comes in mind for multiplication of matrices is the brute force method that is to take two for loops of rows and columns and then inner loop for calculating the product of the elements and then taking sum of them. But, the complexity of this method is O(n^3).

To improve the time complexity of the program, we can consider the approach of sparse matrix.

Sparse matrix is in which the number of non-zero elements is fewer than the number of zero elements. Therefore, to reduce the time of multiplication we can skip the multiplication of zero and use the non-zero numbers to compute the result.

Now, let's dive into the steps of this algorithm:

Algorithm:

1. Define a function sparse_multiplication() that will take two sparse matrices as input, A and B.
2. Extract the row and column of A and B for easy use later.
3. Define an empty list, result, to store the product of matrices.
4. Define a helper function, dot_product(), that will return the dot product of two lists, row and col, which we will use to calculate the product.
5. Create a dictionary, nzA, to store non-zero elements of matrix A with their row and column numbers.
6. Loop for row in range(rowA) and colB in range(colB) to iterate through the rows of A and columns of B.
7. Define an empty list col for later use.
8. For i in nzA.keys(), check if colB equal to the column of i in matrix B.
9. If it is true, append the value of i to col list.
10. Call dot_product() with two parameters nzA[i] and B[c].
11. Append the result of dot_product() to the corresponding element in result.
12. Return the result in the format of a list of lists.

Code: def sparse_multiplication(A, B): rowA, colA = len(A), len(A[0]) rowB, colB = len(B), len(B[0]) result = [[0] * colB for _ in range(rowA)]

def dot_product(row, col):
    return sum([row[i] * col[i] for i in range(len(row))])

nzA = {}
for row in range(rowA):
    nzA[row] = {}
    for col in range(colA):
        if A[row][col] != 0:
            nzA[row][col] = A[row][col]

for row in range(rowA):
    for colB in range(colB):
        col = []
        for i in nzA[row].keys():
            if colB == i: col.append(nzA[row][i])
        result[row][colB] = dot_product(col, [x[colB] for x in B])

return result

Time Complexity: The time complexity of this algorithm is O(n^2) as we are looping through the rows of A and the columns of B.

Space Complexity: The space complexity of this algorithm is also O(n^2) because we are creating a dictionary and a list of lists to store values.

Conclusion: In this article, we learned about the sparse matrix multiplication problem, a method to solve the problem using dictionaries and lists, and the time and space complexity of the algorithm.

1