LeetCode Solutions Blog

Sparse Matrix Multiplication

Number: 311

Difficulty: Medium

Paid? Yes

Problem Description

Given two sparse matrices mat1 of dimensions m x k and mat2 of dimensions k x n, return the product matrix mat1 x mat2.

Key Insights

Exploit sparsity by iterating only over non-zero elements.
For each non-zero element in mat1, multiply it with corresponding non-zero elements in mat2.
Accumulate the product into the result matrix.
This approach reduces unnecessary multiplication operations when many elements are zero.

Space and Time Complexity

Time Complexity: O(m * k * n) in the worst-case, but significantly lower when many elements are zero. Space Complexity: O(m * n) for the resulting matrix.

Solution

We loop through each row of mat1 and for every non-zero element, we traverse the corresponding row in mat2. By checking if an element in both matrices is non-zero before multiplying, we avoid redundant calculations. This optimization leverages the sparsity of the matrices. We use standard nested loops along with conditional checks to implement this efficient multiplication.

Code Solutions

def sparseMatrixMultiplication(mat1, mat2):
    # Get dimensions of mat1 and mat2
    m, k = len(mat1), len(mat1[0])
    n = len(mat2[0])
    # Initialize result matrix with zeros
    result = [[0] * n for _ in range(m)]
    
    # Iterate through each row in mat1
    for i in range(m):
        # For each element in row i of mat1
        for p in range(k):
            if mat1[i][p] != 0:  # Only consider non-zero element in mat1
                # Multiply with corresponding elements in the row of mat2
                for j in range(n):
                    if mat2[p][j] != 0:  # Only consider non-zero element in mat2
                        result[i][j] += mat1[i][p] * mat2[p][j]
    return result

# Example usage:
print(sparseMatrixMultiplication([[1,0,0],[-1,0,3]], [[7,0,0],[0,0,0],[0,0,1]]))