# [C++] Using hash tables (unordered_maps)

• ``````vector<vector<int>> multiply(vector<vector<int>> &A, vector<vector<int>> &B) {
int m = A.size(), n = m ? A[0].size() : 0, p = n ? B[0].size() : 0;
if (!m || !n || !p) return {};

unordered_map<int, list<pair<int, int>>> htA, htB;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (A[i][j])
htA[i].emplace_back(j, A[i][j]);
for (int i = 0; i < n; i++)
for (int j = 0; j < p; j++)
if (B[i][j])
htB[j].emplace_back(i, B[i][j]);

vector<vector<int>> res (m, vector<int> (p, 0));
for (int i = 0; i < m; i++) {
for (int j = 0; j < p; j++) {
auto foundA = htA.find(i), foundB = htB.find(j);
if (foundA != htA.end() && foundB != htB.end()) {
auto l1 = foundA->second, l2 = foundB->second;
auto it1 = l1.begin(), it2 = l2.begin();
while (it1 != l1.end() && it2 != l2.end()) {
if (it1->first == it2->first) {
res[i][j] += it1->second * it2->second;
it1++; it2++;
}
else if (it1->first < it2->first) it1++;
else it2++;
}
}
}
}
return res;
}
``````

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