Sparse Matrix Multiplication

class Solution:
    """
    Multiplies two matrices using sparse matrix representation.

    Time Complexity:
    ----------------
    O(m1 * n1 + m2 * n2 + m1 * nonzero_col_mat1 * nonzero_col_mat2)
    - m1, n1: dimensions of mat1
    - m2, n2: dimensions of mat2
    - k: average non-zero elements per row in mat1

    Space Complexity:
    -----------------
    O(m1 * n1 + m2 * n2 + m1 * n2)
    - Space for sparse matrices and result matrix.
    """
    def solve(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:

        sparse_mat1 = self.create_dense_matrix(mat1)
        sparse_mat2 = self.create_dense_matrix(mat2)
        m, n = len(mat1), len(mat2[0])
        result_matrix = [[0] * n for _ in range(m)]

        for i in range(m):
            for col_index_mat1, value_mat1 in sparse_mat1[i]:
                for col_index_mat2, value_mat2 in sparse_mat2[col_index_mat1]:
                    result_matrix[i][col_index_mat2] += value_mat1 * value_mat2

        return result_matrix

    def create_dense_matrix(self, matrix: List[List[int]]) -> List[List[tuple]]:
        dense_matrix = [[] for _ in range(len(matrix))]
        for row_index, row in enumerate(matrix):
            for col_index, value in enumerate(row):
                if value:
                    dense_matrix[row_index].append((col_index, value))
        return dense_matrix