311.Sparse_Matrix_Multiplication(Medium).md

311. Sparse Matrix Multiplication (Medium)

Date and Time: Apr 3, 2025

Link: https://leetcode.com/problems/sparse-matrix-multiplication

Question:

Given two sparse matrices mat1 of size m x k and mat2 of size k x n, return the result of mat1 x mat2. You may assume that multiplication is always possible.

Example 1:

Input: mat1 = [[1,0,0],[-1,0,3]], mat2 = [[7,0,0],[0,0,0],[0,0,1]]
Output: [[7,0,0],[-7,0,3]]

Example 2:

Input: mat1 = [[0]], mat2 = [[0]]
Output: [[0]]

Constraints:

• m == mat1.length

• k == mat1[i].length == mat2.length

• n == mat2[i].length

• 1 <= m, n, k <= 100

• -100 <= mat1[i][j], mat2[i][j] <= 100

Walk-through:

Optimized:
We save each matrix's nonzero element into a dictionary by their row with [val, col], so we have {row: [[v1, c1], [v2, c2]]}.

After that, we can start processing each row with nonzero elements from mat1. Because the dimension of two matrices are m x k and k x n, so the column in mat1 corresponds to the row in mat2. We can use the nonzero element's col from mat1 row to multiply the nonzero element's col from mat2.

Hence, we can save space waster when a matrix is too big with few non-zero elements.

Optimized:

The interviewer's follow-up could be, what if the matrix is too big to store in the memory, but there are only a few non-zero elements. Here, he wants to see how we handle huge space waste. He expects us to store the matrix efficiency and do multiplication using that.

class Solution:
    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:
        # Save {row: [val, col]}
        # All elements from row mat1 * all elements on row1 mat2
        # Use each row from mat1 * every row in mat2, multiply if they have the same col, and update res[r][c]

        # mat1: {0: [1, 0], 
        #        1: [[-1, 0], [3, 2]]}
        # mat2: {0: [7, 0], 
        #        2: [1, 2]}

        # TC: O(m * k * n), SC: O(m * n)
        # Fill in mat1, mat2 into dict
        def matrix_dict(matrix):
            mat_dict = collections.defaultdict(list)
            for r in range(len(matrix)):
                for c in range(len(matrix[0])):
                    if matrix[r][c] != 0:
                        mat_dict[r].append([matrix[r][c], c])
            return mat_dict

        mat1_dict, mat2_dict = matrix_dict(mat1), matrix_dict(mat2)
        res = [[0] * len(mat2[0]) for _ in range(len(mat1))]    # m * n matrix
        # Fill in res matrix
        for r in range(len(mat1)):
            # Access val, col from mat1
            for v1, c1 in mat1_dict[r]:
                # One row from mat1 * every row from mat2, c1 the row number in mat2
                for v2, c2 in mat2_dict[c1]:
                    # Update res by mat1's row and mat2's col
                    res[r][c2] += v1 * v2
        return res

Time Complexity: $O(m * k * n)$
Space Complexity: $O(m * n)$

Row by row with checking 0 optimization

class Solution:
    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:
        # S: new matrix will have m rows x n cols

        # Same as each row x each row, then take the sum
        # TC: O(m * k * n), SC: O(mxn)

        res = [[0] * len(mat2[0]) for _ in range(len(mat1))]
        for r1 in range(len(mat1)):     # r1 = 0
            lst = []       # [7,]
            # mat2
            for r2 in range(len(mat2)):
                for c in range(len(mat2[r2])):
                    # Skip if mat1[r][c] = 0
                    if mat1[r1][c] != 0:
                        res[r1][c] += mat1[r1][c] * mat2[r2][c]
        return res

Time Complexity: $O(mnk)$
Space Complexity: $O(m*n)$

Brute Force:

class Solution:
    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:
        # Each row from mat1 * each col from mat2
        # Nested Loop to update entry in result matrix
        # TC: O(m * k * n), SC: O(m * n)
        m, k, n = len(mat1), len(mat1[0]), len(mat2[0])
        res = [[0] * n for _ in range(m)]       # m * n matrix
        for r in range(m):
            for c in range(n):
                val = 0
                for i in range(k):
                    val += mat1[r][i] * mat2[i][c]
                # Update val in res[r][c]
                res[r][c] = val
        return res

Time Complexity: $O(mnk)$
Space Complexity: $O(m*n)$