NUHMAN.com

Introduction

LeetCode 311: Sparse Matrix Multiplication involves multiplying two sparse matrices. A sparse matrix is a matrix in which most of the elements are zero. Matrix multiplication is a standard operation in many fields, including data science and computer graphics. However, in this problem, the goal is to compute the multiplication efficiently by taking advantage of the sparse nature of the matrices, which can significantly reduce the number of operations needed.

In sparse matrix multiplication, we focus only on the non-zero elements to avoid redundant computations, making the solution much more efficient.

Problem Statement

You are given two sparse matrices A and B. The matrix A has dimensions m x k and the matrix B has dimensions k x n. The resulting matrix will have dimensions m x n. You are tasked with returning the product of the matrices A and B. The result should be a matrix of the same size as the resulting product.

Note:

• A[i][j] is the value of the matrix A at the i-th row and j-th column.
• B[i][j] is the value of the matrix B at the i-th row and j-th column.
• If an element in matrix A or B is zero, ignore it during the computation.

Example

python

# Example 1
Input: A = [[1,0,0], [-1,0,3]], B = [[7,0,0], [0,0,0], [0,0,1]]
Output: [[7,0,0], [-7,0,3]]

Explanation:
A = [[1,0,0], [-1,0,3]]
B = [[7,0,0], [0,0,0], [0,0,1]]
The product is:
    [[1*7 + 0*0 + 0*0, 1*0 + 0*0 + 0*0, 1*0 + 0*0 + 0*1], 
     [-1*7 + 0*0 + 3*0, -1*0 + 0*0 + 3*0, -1*0 + 0*0 + 3*1]]
= [[7, 0, 0], [-7, 0, 3]]

# Example 2
Input: A = [[0]], B = [[1]]
Output: [[0]]

Step-by-Step Solution

🧠 Intuition

Given two matrices, A and B, to multiply them, we perform the standard matrix multiplication operation:

C[i][j]=∑k=0k−1A[i][k]∗B[k][j]C[i][j] = \sum_{k=0}^{k-1} A[i][k] * B[k][j]C[i][j]=k=0∑k−1​A[i][k]∗B[k][j]Where C[i][j] is the resulting element in the i-th row and j-th column of the product matrix.

However, since both matrices are sparse, many elements are zero, so we don't need to perform multiplications for the zero elements. Instead, we focus only on the non-zero elements in A and B, which can reduce the computation time and make the multiplication more efficient.

✅ Approach

1. Iterate through each non-zero element in A: We only need to consider the non-zero elements of A. For each non-zero element A[i][k], we can multiply it with the corresponding elements in B[k][j].
2. Multiply and accumulate: For each non-zero element A[i][k], multiply it with the corresponding element B[k][j] and add the result to the corresponding position in the result matrix C[i][j].
3. Efficient computation: By skipping the zero elements in both matrices, the time complexity is reduced significantly, especially when dealing with large sparse matrices.

✅ Python Code

python

class Solution:
    def multiply(self, A: list[list[int]], B: list[list[int]]) -> list[list[int]]:
        m, k = len(A), len(A[0])  # Dimensions of matrix A
        k, n = len(B), len(B[0])  # Dimensions of matrix B
        # Initialize the result matrix with zeros
        result = [[0] * n for _ in range(m)]
        
        # Iterate over each non-zero element of A
        for i in range(m):
            for k_idx in range(k):
                if A[i][k_idx] != 0:  # Skip zero elements
                    # For each non-zero element A[i][k_idx], multiply with B
                    for j in range(n):
                        result[i][j] += A[i][k_idx] * B[k_idx][j]
        
        return result

Explanation of the Code

1. Matrix Dimensions:

• We first get the dimensions of the matrices A and B. A has dimensions m x k and B has dimensions k x n.

1. Result Matrix Initialization:

• We initialize a result matrix result of dimensions m x n with all values set to zero.

1. Main Loop:

• We iterate through each element in A. If the element A[i][k] is non-zero, we compute the contributions to the result matrix result[i][j] by multiplying the non-zero element A[i][k] with corresponding elements from B[k][j].

1. Return the Result:

• After all iterations, the result matrix contains the final product of matrices A and B, which we return.

⏱️ Time and Space Complexity

MetricValueTime ComplexityO(m * k * n)Space ComplexityO(m * n)

• Time Complexity: The algorithm loops through each non-zero element in A and performs multiplication and addition for the corresponding elements in B. The worst-case time complexity is O(m * k * n), where m is the number of rows in A, n is the number of columns in B, and k is the common dimension between A and B.
• Space Complexity: We use a result matrix result of dimensions m x n, which takes O(m * n) space.

🔍 Edge Cases

1. Zero Matrices:

• If either A or B is a zero matrix, the result will also be a zero matrix.

1. Single Element Matrices:

• If A and B are both 1 x 1 matrices, the multiplication is straightforward.

1. Empty Matrices:

• If either A or B is empty, the result should also be an empty matrix.

✅ Conclusion

LeetCode 311: Sparse Matrix Multiplication is a problem where we multiply two sparse matrices efficiently by focusing on their non-zero elements. By avoiding operations on zero elements, the solution becomes significantly faster than the naive matrix multiplication approach. This solution is implemented using a triple-nested loop, optimized to only consider non-zero values.