• Time:O(mnl)
• Space:O(nl)

## C++

class Solution {
public:
vector<vector<int>> multiply(vector<vector<int>>& mat1,
vector<vector<int>>& mat2) {
const int m = mat1.size();
const int n = mat2.size();
const int l = mat2[0].size();
vector<vector<int>> ans(m, vector<int>(l));

for (int i = 0; i < m; ++i)
for (int j = 0; j < l; ++j)
for (int k = 0; k < n; ++k)
ans[i][j] += mat1[i][k] * mat2[k][j];

return ans;
}
};


## JAVA

class Solution {
public int[][] multiply(int[][] mat1, int[][] mat2) {
final int m = mat1.length;
final int n = mat2.length;
final int l = mat2[0].length;
int[][] ans = new int[m][l];

for (int i = 0; i < m; ++i)
for (int j = 0; j < l; ++j)
for (int k = 0; k < n; ++k)
ans[i][j] += mat1[i][k] * mat2[k][j];

return ans;
}
}


## Python

class Solution:
def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:
m = len(mat1)
n = len(mat2)
l = len(mat2[0])
ans = [[0] * l for _ in range(m)]

for i in range(m):
for j in range(l):
for k in range(n):
ans[i][j] += mat1[i][k] * mat2[k][j]

return ans


## Approach 2: Look up

• Time:O(nl + mn \times \text{nonZero}(B))
• Space:O(ml + \text{nonZero}(B))

## C++

class Solution {
public:
vector<vector<int>> multiply(vector<vector<int>>& mat1,
vector<vector<int>>& mat2) {
const int m = mat1.size();
const int n = mat2.size();
const int l = mat2[0].size();
vector<vector<int>> ans(m, vector<int>(l));
vector<vector<int>> nonZeroColIndicesInMat2;

for (int i = 0; i < n; ++i) {
vector<int> colIndices;
for (int j = 0; j < l; ++j)
if (mat2[i][j] != 0)
colIndices.push_back(j);
nonZeroColIndicesInMat2.push_back(colIndices);
}

for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) {
if (mat1[i][j] == 0)
continue;
// mat1's j-th column matches mat2's j-th row
for (const int colIndex : nonZeroColIndicesInMat2[j])
ans[i][colIndex] += mat1[i][j] * mat2[j][colIndex];
}

return ans;
}
};


## JAVA

class Solution {
public int[][] multiply(int[][] mat1, int[][] mat2) {
final int m = mat1.length;
final int n = mat2.length;
final int l = mat2[0].length;
int[][] ans = new int[m][l];
List<Integer>[] nonZeroColIndicesInMat2 = new List[n];

for (int i = 0; i < n; ++i) {
List<Integer> colIndices = new ArrayList<>();
for (int j = 0; j < l; ++j)
if (mat2[i][j] != 0)
nonZeroColIndicesInMat2[i] = colIndices;
}

for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) {
if (mat1[i][j] == 0)
continue;
// mat1's j-th column matches mat2's j-th row
for (final int colIndex : nonZeroColIndicesInMat2[j])
ans[i][colIndex] += mat1[i][j] * mat2[j][colIndex];
}

return ans;
}
}


## Python

class Solution:
def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:
m = len(mat1)
n = len(mat2)
l = len(mat2[0])
ans = [[0] * l for _ in range(m)]
nonZeroColIndicesInMat2 = [
[j for j, a in enumerate(row) if a]
for row in mat2
]

for i in range(m):
for j, a in enumerate(mat1[i]):
if a == 0:
continue
# mat1's j-th column matches mat2's j-th row
for colIndex in nonZeroColIndicesInMat2[j]:
ans[i][colIndex] += a * mat2[j][colIndex]

return ans