Easy Python Solution Exploring Sparse Property


  • 0
    J

    Say Matrix A is MN, Matrix B is NL, then the total computation using ordinary method is O(MNL).
    However, for every 0 in matrix A, there are L wasted computation.
    We can represent matrix A as (i, j, val) where val must be none zero. We can use dictionary to represent matrix A, using row i as key, and (j, val) as value.

    class Solution(object):
        def multiply(self, A, B):
            """
            :type A: List[List[int]]
            :type B: List[List[int]]
            :rtype: List[List[int]]
            """
            hashRowA = {}
        
            for i, row in enumerate(A):
                t = []
                for j,val in enumerate(row):
                    if val != 0:
                        t.append((j,val))
                hashRowA[i] = t
        
        
            result = []
            index = 0
            for x in range(len(A)):
                result.append([0]*len(B[0]))
        
            for i in range(len(A)):
                for y in range(len(B[0])):
                    for j, val in hashRowA[i]:
                        result[i][y] += val*B[j][y]
                        index += 1
            return result
    

    Generate the dictionary for A is O(MN). Say we have X number of none zero value in matrix A, then the computation part is LX. where X is << M*N if matrix is sparse.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.