I don't think for this problem there is a real need of a hashmap. It is only for pedagogical purpose.
Creating the hashmap representation of the matrix takes allready O(m*n) time. It is simply sufficient to verify if the elements are 0 before trying to multiply them.
It is much faster then creating the hashmaps
int m = A.size(); int n = B.size(); int p = B.size(); vector<vector<int>> result(m,vector<int>(p,0)); for(int i = 0; i < m; i++) for(int k = 0; k < n; k++) if(A[i][k] != 0) for(int j = 0; j < p; j++) if(B[k][j] != 0) result[i][j] += A[i][k] * B[k][j]; return result;