Given two Sparse Matrix A and B, return the result of AB.

You may assume that A's column number is equal to B's row number.

Have you met this question in a real interview?

Yes

Example

A = [
  [ 1, 0, 0],
  [-1, 0, 3]
]

B = [
  [ 7, 0, 0 ],
  [ 0, 0, 0 ],
  [ 0, 0, 1 ]
]


     |  1 0 0 |   | 7 0 0 |   |  7 0 0 |
AB = | -1 0 3 | x | 0 0 0 | = | -7 0 3 |
                  | 0 0 1

method 1:

calculate one row in the answer at a time

def multiply(self, A, B):
        # write your code here

        n = len(A)
        t = len(A[0])
        m = len(B[0])

        ans = [[0 for j in xrange(m)] for i in xrange(n)]
        #the calculation order is calculate one row in the final ans matrix at a time

        for i in xrange(n):
            for k in xrange(t):
                for j in xrange(m):
                    ans[i][j] += A[i][k] * B[k][j]

        return ans

method 2:

since we are calculating one row in the answer at a time, so we are using the element in A to multiple each element in B for the corresponding row, so if A is zero, no need to proceed

A = [
  [ 1, 0, 0],
  [-1, 0, 3]
]

B = [
  [ 7, 0, 0 ],
  [ 0, 0, 0 ],
  [ 0, 0, 1 ]
]

so for example the first line is
A[0][0] * B[0][0],  A[0][0] * B[0][1], A[0][0] * B[0][2]
       +                    +                  +
A[0][1] * B[1][0],  A[0][1] * B[1][1], A[0][1] * B[1][2]
       +                    +                  +
A[0][2] * B[2][0],  A[0][2] * B[2][1], A[0][2] * B[2][2]


as we can see here the element A[i][k] is going to be multiplied with each element in B[k][j]
so if A[i][k] is zero, no need to proceed


def multiply(self, A, B):
        # write your code here

        n = len(A)
        t = len(A[0])
        m = len(B[0])

        ans = [[0 for j in xrange(m)] for i in xrange(n)]
        #the calculation order is calculate one row in the final ans matrix at a time

        for i in xrange(n):
            for k in xrange(t):
                if not A[i][k]:
                    continue
                for j in xrange(m):
                    ans[i][j] += A[i][k] * B[k][j]

        return ans

method 3

A = [
  [ 1, 0, 0],
  [-1, 0, 3]
]

B = [
  [ 7, 0, 0 ],
  [ 0, 0, 0 ],
  [ 0, 0, 1 ]
]

so for example the first line is
A[0][0] * B[0][0],  A[0][0] * B[0][1], A[0][0] * B[0][2]
       +                    +                  +
A[0][1] * B[1][0],  A[0][1] * B[1][1], A[0][1] * B[1][2]
       +                    +                  +
A[0][2] * B[2][0],  A[0][2] * B[2][1], A[0][2] * B[2][2]


for each row in B, if we remember only the non-zero element, then we can only apply them to A[i][k]

def multiply(self, A, B):
        # write your code here

        n = len(A)
        t = len(A[0])
        m = len(B[0])

        ans = [[0 for j in xrange(m)] for i in xrange(n)]
        #the calculation order is calculate one row in the final ans matrix at a time

        #remember all of the non-zero index in b for each row
        aux = [[j for j in xrange(m) if B[i][j] != 0] for i in xrange(len(B))]

        for i in xrange(n):
            for k in xrange(t):
                #so here A[i][k] needs to multiple with each B[k][j] so if A[i][k] is 0 then, no need to proceed
                #we can go directly to next k
                if not A[i][k]:
                    continue
                for j in aux[k]:
                    ans[i][j] += A[i][k] * B[k][j]

        return ans