# Easiest JAVA solution

• UPDATE: Thanks to @stpeterh we have this `70ms` concise solution:

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

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

The followings is the original `75ms` solution:

The idea is derived from a CMU lecture.

A sparse matrix can be represented as a sequence of rows, each of which is a sequence of (column-number, value) pairs of the nonzero values in the row.

So let's create a non-zero array for A, and do multiplication on B.

Hope it helps!

``````public int[][] multiply(int[][] A, int[][] B) {
int m = A.length, n = A[0].length, nB = B[0].length;
int[][] result = new int[m][nB];

List[] indexA = new List[m];
for(int i = 0; i < m; i++) {
List<Integer> numsA = new ArrayList<>();
for(int j = 0; j < n; j++) {
if(A[i][j] != 0){
}
}
indexA[i] = numsA;
}

for(int i = 0; i < m; i++) {
List<Integer> numsA = indexA[i];
for(int p = 0; p < numsA.size() - 1; p += 2) {
int colA = numsA.get(p);
int valA = numsA.get(p + 1);
for(int j = 0; j < nB; j ++) {
int valB = B[colA][j];
result[i][j] += valA * valB;
}
}
}

return result;
}
``````

• Thanks for providing this nice solution, @yavinci. I have a question about it. It seems like the CMU lecture solution is for sparse matrix multiplies dense vector. And I guess "another non-zero array on B" could be useful. The reason is that, for an element `[k, j]` in B, it would be detected for non-zero elements several times on the fly, depending on how many `i`'s make elements `[i, k]` non-zero in A. However, your solution is faster than my Java solution with two HashMaps. I guess the reason could be the efficiency of primitive types in your solution.

• Thanks for you suggestion! Will try to improve it based on ours.

• Moreover, I guess the set of test cases is not good enough right now. Your solution inspired me to detecting both on the fly: storing non-zero elements in A in a List of Lists and then detecting B and do multiplication is kind of like detecting both on the fly. I tried in python, such a direct detection solution could be fast:

``````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
``````

• Thanks! Can you use code shortcut for your code? Command + K?

• Sorry for that. And thanks for teaching the way to edit it :-).

• And the corresponding Java solution takes ~70ms:

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

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

• I do think that probably the test set is not good enough right now. There are only 12 test cases.

• Amazing solution! This is so short. Better than mine. But... why this is so similar to the default implementation of multiplication.

• Thanks for your encouragement. I probably will update my old post, after I try with only having a table for B. Now I think probably we can detect B in advance and then detect A on the fly to do multiplications and additions.

• Thanks for sharing your solution. Will upvote yours once you posted.

• Why are you so hard working at Thanksgiving? Happy Thanksgiving, by the way!

• Happy Thanksgiving, yavinci :-) I felt I worked so hard too. So I just watched `The Martian`. It is pretty good. Based on our discussion, I updated my solution. Thanks again for discussing with me.

• Nice discussing with you too! It looks like you have 6 solutions, which again demonstrate how hardcore you are today. `Mission: Impossible` is really good too. You should take a look. Now you've learnt using command + K, even if you tagged a movie name.

• Yes, I have not watched the 2015 `Mission: Impossible`, and would like to watch it. I am looking forward to watch the `Star Wars: The Force Awakens` as well.

• Yeah. Me too!

• Isn't this like a brute force solution?

• Thanks a lot for sharing, I have the same question as GWTW above, isn't this brute force? Can you help explain a bit?

• Great solution!
based on your second idea from CMU lecture, c++ implementation, 32 ms.

`````` vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
const int rowA = A.size(), rowB = B.size();
const int colA = A[0].size(), colB = B[0].size();
vector<vector<int>> res(rowA, vector<int>(colB, 0));
vector<vector<pair<int, int>>> sparseA(rowA, vector<pair<int,int>>());

for(int i = 0; i < rowA; i++)
for(int j = 0; j < colA; j++) {
if(A[i][j] != 0)  sparseA[i].emplace_back(j, A[i][j]);
}
for (int i = 0; i < rowA; ++i)
for (auto noZeros : sparseA[i])
for (int j = 0; j < rowB; ++j) {
if(B[noZeros.first][j] != 0) res[i][j] += noZeros.second * B[noZeros.first][j];
}
return res;
}``````

• @lchen77, very fast solution. Thanks for sharing!

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