# Java and Python Solutions with and without Tables

• Given A and B are sparse matrices, we could use lookup tables to speed up. At the beginining I thought two lookup tables would be necessary. After discussing with @yavinci, I think one lookup table for B would be enough. Surprisingly, it seems like detecting non-zero elements for both A and B on the fly without additional data structures provided the fastest performance on current test set.

However, I think such fastest performance could due to an imperfect test set we have for OJ right now: there are only 12 test cases. And, for an element `B[k, j]`, it would be detected for non-zero elements several times if we detecting both A and B on the fly, depending on how many `i`'s make elements `A[i, k]` non-zero. With this point, the additional data structures, like lookup tables, should save our time by focusing on only non-zero elements. If it is not, I am worried the set of OJ test cases probably is not good enough.

Anyway, I am posting my respective solutions below. Comments are welcome. Thanks @yavinci again for discussing with me.

Python solution with only one table for B (~196ms):

``````class Solution(object):
def multiply(self, A, B):
"""
:type A: List[List[int]]
:type B: List[List[int]]
:rtype: List[List[int]]
"""
if A is None or B is None: return None
m, n, l = len(A), len(A[0]), len(B[0])
if len(B) != n:
raise Exception("A's column number must be equal to B's row number.")
C = [[0 for _ in range(l)] for _ in range(m)]
tableB = {}
for k, row in enumerate(B):
tableB[k] = {}
for j, eleB in enumerate(row):
if eleB: tableB[k][j] = eleB
for i, row in enumerate(A):
for k, eleA in enumerate(row):
if eleA:
for j, eleB in tableB[k].iteritems():
C[i][j] += eleA * eleB
return C
``````

Java solution with only one table for B (~150ms):

``````public class Solution {
public int[][] multiply(int[][] A, int[][] B) {
if (A == null || A[0] == null || B == null || B[0] == null) return null;
int m = A.length, n = A[0].length, l = B[0].length;
int[][] C = new int[m][l];
Map<Integer, HashMap<Integer, Integer>> tableB = new HashMap<>();

for(int k = 0; k < n; k++) {
tableB.put(k, new HashMap<Integer, Integer>());
for(int j = 0; j < l; j++) {
if (B[k][j] != 0){
tableB.get(k).put(j, B[k][j]);
}
}
}

for(int i = 0; i < m; i++) {
for(int k = 0; k < n; k++) {
if (A[i][k] != 0){
for (Integer j: tableB.get(k).keySet()) {
C[i][j] += A[i][k] * tableB.get(k).get(j);
}
}
}
}
return C;
}
}
``````

Python solution without table (~156ms):

``````class Solution(object):
def multiply(self, A, B):
"""
:type A: List[List[int]]
:type B: List[List[int]]
:rtype: List[List[int]]
"""
if A is None or B is None: return None
m, n, l = len(A), len(A[0]), len(B[0])
if len(B) != n:
raise Exception("A's column number must be equal to B's row number.")
C = [[0 for _ in range(l)] for _ in range(m)]
for i, row in enumerate(A):
for k, eleA in enumerate(row):
if eleA:
for j, eleB in enumerate(B[k]):
if eleB: C[i][j] += eleA * eleB
return C
``````

Java solution without table (~70ms):

``````public class Solution {
public int[][] multiply(int[][] A, int[][] B) {
int m = A.length, n = A[0].length, l = B[0].length;
int[][] C = new int[m][l];

for(int i = 0; i < m; i++) {
for(int k = 0; k < n; k++) {
if (A[i][k] != 0){
for (int j = 0; j < l; j++) {
if (B[k][j] != 0) C[i][j] += A[i][k] * B[k][j];
}
}
}
}
return C;
}
}
``````

Python solution with two tables (~196ms):

``````class Solution(object):
def multiply(self, A, B):
"""
:type A: List[List[int]]
:type B: List[List[int]]
:rtype: List[List[int]]
"""
if A is None or B is None: return None
m, n = len(A), len(A[0])
if len(B) != n:
raise Exception("A's column number must be equal to B's row number.")
l = len(B[0])
table_A, table_B = {}, {}
for i, row in enumerate(A):
for j, ele in enumerate(row):
if ele:
if i not in table_A: table_A[i] = {}
table_A[i][j] = ele
for i, row in enumerate(B):
for j, ele in enumerate(row):
if ele:
if i not in table_B: table_B[i] = {}
table_B[i][j] = ele
C = [[0 for j in range(l)] for i in range(m)]
for i in table_A:
for k in table_A[i]:
if k not in table_B: continue
for j in table_B[k]:
C[i][j] += table_A[i][k] * table_B[k][j]
return C
``````

Java solution with two tables (~160ms):

``````public class Solution {
public int[][] multiply(int[][] A, int[][] B) {
if (A == null || B == null) return null;
if (A[0].length != B.length)
throw new IllegalArgumentException("A's column number must be equal to B's row number.");
Map<Integer, HashMap<Integer, Integer>> tableA = new HashMap<>();
Map<Integer, HashMap<Integer, Integer>> tableB = new HashMap<>();
int[][] C = new int[A.length][B[0].length];
for (int i = 0; i < A.length; i++) {
for (int j = 0; j < A[i].length; j++) {
if (A[i][j] != 0) {
if(tableA.get(i) == null) tableA.put(i, new HashMap<Integer, Integer>());
tableA.get(i).put(j, A[i][j]);
}
}
}

for (int i = 0; i < B.length; i++) {
for (int j = 0; j < B[i].length; j++) {
if (B[i][j] != 0) {
if(tableB.get(i) == null) tableB.put(i, new HashMap<Integer, Integer>());
tableB.get(i).put(j, B[i][j]);
}
}
}

for (Integer i: tableA.keySet()) {
for (Integer k: tableA.get(i).keySet()) {
if (!tableB.containsKey(k)) continue;
for (Integer j: tableB.get(k).keySet()) {
C[i][j] += tableA.get(i).get(k) * tableB.get(k).get(j);
}
}
}
return C;
}
}
``````

• what is the time complexity of these methods please?

• One potential advantage of having two hash tables is that it can be used as a sparse matrix representation. The the code becomes more reusable and extensible.

• @stpeterh How about this? If we traverse A column by column instead of row by row then we don't need to use a HashMap:

``````import java.util.*;

public class Solution {

public int[][] multiply(int[][] A, int[][] B) {
if (A == null || A[0] == null || B == null || B[0] == null) return null;
int m = A.length, n = A[0].length, l = B[0].length;
int[][] C = new int[m][l];

//for each column in A
for(int k = 0; k < n; k++) {

//compute the non-zero slots in row k in B:

//for each slot in column k in A
for(int i = 0; i < m; i++) {

if(A[i][k] != 0) {
//for each non-zero slot in row k in B
for(BSlot bSlot: nonZerosInB) {
C[i][bSlot.j] += A[i][k] * bSlot.value;
}
}
}
}

return C;
}

//returns linked list of non-zeros in B's row k
LinkedList<BSlot> nonZerosInRowKInB(int[][] B, int k) {
//compute the non-zero slots in row k in B:

//for each slot in row k in B
for(int j = 0; j < B[0].length; j++) {
if (B[k][j] != 0){
//we need to save the column (j) and the value of the slot (B[k][j])
BSlot bSlot = new BSlot(j, B[k][j]);
}
}
return nonZerosInB;
}

}

//non-zero slot in matrix B
class BSlot {
int j; //column
int value;

BSlot(int j, int value) {
this.j = j;
this.value = value;
}
}
``````

• @stpeterh
Hello, why dose the tag contain HashTable, I didn't see the advantage of it.
I fount this post, with or without table, the time complexity is still O(n^3).
Than why we wanna extra space?
https://discuss.leetcode.com/topic/30625/easiest-java-solution/9

• HashMap can reduce the theoretic complexity, however HashMap in Java is relatively slow, I think it is why the first solution is slower than second one.

• Hi, I think because you still need to go through the whole matrix A, so the final complexity is at least m*n (suppose A is m*n, B is n*l)

Why not choose the element of A by the active cell of B instead. Suppose for a sparse matrix, the avg number of active cell in a column is less than 1. Now we only have l column active numbers. We can now pick the corresponding number from A for less than l times for m rows, which is less than m*l times in total. Well, it depends on how sparse the matrix is.

Tell me if I am wrong.

• This post is deleted!

• Java solution with only one table for A ~155ms

``````public class Solution {
public int[][] multiply(int[][] A, int[][] B) {
int m = A.length, g = A[0].length, n = B[0].length;
Map<Integer, HashMap<Integer, Integer>> mapA = new HashMap<>();
int[][] c = new int[m][n];
// Map<Integer, HashMap<Integer, Integer>> mapB = new HashMap<>();
for (int i = 0; i < m; ++i) {
HashMap<Integer, Integer> tmp = new HashMap<>();
for (int j = 0; j < g; ++j) {
if (A[i][j] != 0) tmp.put(j, A[i][j]);
}
mapA.put(i, tmp);
}
// Multiplication
for (int i = 0; i < m; ++i) {
HashMap<Integer, Integer> tmp = mapA.get(i);
for (Integer k : tmp.keySet()) {
for (int j = 0; j < n; ++j) c[i][j] += tmp.get(k) * B[k][j];
}
}
return c;
}
}
``````

• Nice explanations. It is even better if we can use a convert method to preprocess A and B to reduce redundant code.
Anyone who can figure out the time complexity of the 3 approaches? You can make assumption such as for a nXn sparse matrix, it
has O(n) nonzero elements and start to derive big O from there.

``````public class Solution {
public int[][] multiply(int[][] a, int[][] b) {
int m = a.length;
int nB = b[0].length;
int[][] c = new int[m][nB];
Map<Integer, Map<Integer, Integer>> mapA = convert(a);
Map<Integer, Map<Integer, Integer>> mapB = convert(b);
for (int i : mapA.keySet()) {
for (int k : mapA.get(i).keySet()) {
if (!mapB.containsKey(k)) {
continue;
}
for (int j : mapB.get(k).keySet()) {
c[i][j] += mapA.get(i).get(k) * mapB.get(k).get(j);
}
}
}
return c;
}

private Map<Integer, Map<Integer, Integer>> convert(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
Map<Integer, Map<Integer, Integer>> map = new HashMap<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0) {
continue;
}
map.putIfAbsent(i, new HashMap<>());
map.get(i).put(j, matrix[i][j]);
}
}
return map;
}
}
``````

• This post is deleted!

• I think you should store the nonzero elements of B by column instead of row

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