# Easy Python Solution Exploring Sparse Property

• 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.

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