92ms python, faster than 100%


  • 1
    C

    checking with any() definitely speeds things up. Other than that, I used a bit of trick to skip all the zeros in vector multiplication, since the matrix is sparse.

    def multiply(self, A, B):
    
        result=[[0]*len(B[0]) for _ in xrange(len(A))]
    
        #store indexes non-zero elements in each line of B.  Checking with any() first at this point speeds up from 124ms to 96ms
        Bi=[[i for i,v in enumerate(l) if v] if any(l) else [] for l in B]
    
        for i in xrange(len(A)):
            if not any(A[i]):
                continue
            for j in xrange(len(A[0])):
                if A[i][j]:
                    for k in Bi[j]:
                        result[i][k]+=A[i][j]*B[j][k]
    
        return result

Log in to reply
 

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