Easy Python Solution Exploring Sparse Property

  • 0

    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:
                hashRowA[i] = t
            result = []
            index = 0
            for x in range(len(A)):
            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.