Sparse Matrix Multiplication
Sparse Matrix Multiplication is a medium arrays & hashing problem solved with the matrix traversal pattern.
The best approach, optimal (skip zeros with compressed rows), runs in O(m · k + k · n + Z) time and O(k · n) for the compressed rows space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (textbook triple loop) up.
Problem
You are given two integer matrices: mat1 of size m x k and mat2 of size k x n. Return their matrix product, an m x n matrix whose cell (i, c) equals the sum of mat1[i][j] * mat2[j][c] over every j.
Both inputs are sparse: most of their entries are 0. Aim for a solution that does not waste work multiplying zeros.
Examples
Example 1
- Input
mat1 = [[2, 0, 0], [0, 0, -1]], mat2 = [[0, 4], [5, 0], [0, 3]]- Output
[[0, 8], [0, -3]]- Why
- Row 0 only uses 2 * mat2[0] = [0, 8]; row 1 only uses -1 * mat2[2] = [0, -3].
Example 2
- Input
mat1 = [[0, 0]], mat2 = [[7], [9]]- Output
[[0]]- Why
- A row of zeros produces a row of zeros, whatever mat2 holds.
Constraints
mat1ism x kandmat2isk x n1 <= m, n, k <= 100-100 <= mat1[i][j], mat2[i][j] <= 100
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (textbook triple loop) | O(m · k · n) | O(1) extra |
| Optimal (skip zeros with compressed rows) | O(m · k + k · n + Z) | O(k · n) for the compressed rows |
1Brute force (textbook triple loop)
O(m · k · n)Every one of the m · n cells does k multiplications, zero or not.O(1) extraOnly the output matrix is allocated.Compute every cell of the result as the dot product of a row of mat1 with a column of mat2, multiplying zeros along with everything else.
- Create an m x n result filled with 0.
- For each i in [0, m) and c in [0, n), sum
mat1[i][j] * mat2[j][c]over j in [0, k).
class Solution {
public int[][] multiply(int[][] mat1, int[][] mat2) {
int m = mat1.length, k = mat2.length, n = mat2[0].length;
int[][] res = new int[m][n];
for (int i = 0; i < m; i++) {
for (int c = 0; c < n; c++) {
int sum = 0;
for (int j = 0; j < k; j++) sum += mat1[i][j] * mat2[j][c];
res[i][c] = sum;
}
}
return res;
}
}class Solution:
def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:
m, k, n = len(mat1), len(mat2), len(mat2[0])
res = [[0] * n for _ in range(m)]
for i in range(m):
for c in range(n):
total = 0
for j in range(k):
total += mat1[i][j] * mat2[j][c]
res[i][c] = total
return resclass Solution {
public:
vector<vector<int>> multiply(vector<vector<int>>& mat1, vector<vector<int>>& mat2) {
int m = mat1.size(), k = mat2.size(), n = mat2[0].size();
vector<vector<int>> res(m, vector<int>(n, 0));
for (int i = 0; i < m; i++) {
for (int c = 0; c < n; c++) {
int sum = 0;
for (int j = 0; j < k; j++) sum += mat1[i][j] * mat2[j][c];
res[i][c] = sum;
}
}
return res;
}
};function multiply(mat1, mat2) {
const m = mat1.length, k = mat2.length, n = mat2[0].length;
const res = Array.from({ length: m }, () => new Array(n).fill(0));
for (let i = 0; i < m; i++) {
for (let c = 0; c < n; c++) {
let sum = 0;
for (let j = 0; j < k; j++) sum += mat1[i][j] * mat2[j][c];
res[i][c] = sum;
}
}
return res;
}2Optimal (skip zeros with compressed rows)
O(m · k + k · n + Z)Scanning both matrices costs m · k + k · n; Z is the number of non-zero pairs actually multiplied, which is tiny for sparse inputs.O(k · n) for the compressed rowsAt most every entry of `mat2` is stored once in the compressed lists.Row i of the result is the sum of mat1[i][j] times row j of mat2. First store, for every row of mat2, only its non-zero (column, value) pairs. Then for each non-zero mat1[i][j], add its products with those pairs into row i. Zero entries of either matrix are never multiplied.
- For each row j of
mat2, build a list of (column, value) for its non-zero entries. - For each i and j with
mat1[i][j] != 0, for each (c, v) in row j's list, dores[i][c] += mat1[i][j] * v. - Return
res.
class Solution {
public int[][] multiply(int[][] mat1, int[][] mat2) {
int m = mat1.length, k = mat2.length, n = mat2[0].length;
List<List<int[]>> rows = new ArrayList<>();
for (int j = 0; j < k; j++) {
List<int[]> nz = new ArrayList<>();
for (int c = 0; c < n; c++) {
if (mat2[j][c] != 0) nz.add(new int[] { c, mat2[j][c] });
}
rows.add(nz);
}
int[][] res = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < k; j++) {
int a = mat1[i][j];
if (a == 0) continue;
for (int[] e : rows.get(j)) res[i][e[0]] += a * e[1];
}
}
return res;
}
}class Solution:
def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:
m, k, n = len(mat1), len(mat2), len(mat2[0])
rows = [[(c, v) for c, v in enumerate(row) if v != 0] for row in mat2]
res = [[0] * n for _ in range(m)]
for i in range(m):
out = res[i]
for j in range(k):
a = mat1[i][j]
if a == 0:
continue
for c, v in rows[j]:
out[c] += a * v
return resclass Solution {
public:
vector<vector<int>> multiply(vector<vector<int>>& mat1, vector<vector<int>>& mat2) {
int m = mat1.size(), k = mat2.size(), n = mat2[0].size();
vector<vector<pair<int, int>>> rows(k);
for (int j = 0; j < k; j++) {
for (int c = 0; c < n; c++) {
if (mat2[j][c] != 0) rows[j].push_back({c, mat2[j][c]});
}
}
vector<vector<int>> res(m, vector<int>(n, 0));
for (int i = 0; i < m; i++) {
for (int j = 0; j < k; j++) {
int a = mat1[i][j];
if (a == 0) continue;
for (auto& e : rows[j]) res[i][e.first] += a * e.second;
}
}
return res;
}
};function multiply(mat1, mat2) {
const m = mat1.length, k = mat2.length, n = mat2[0].length;
const rows = mat2.map((row) => {
const nz = [];
for (let c = 0; c < n; c++) if (row[c] !== 0) nz.push([c, row[c]]);
return nz;
});
const res = Array.from({ length: m }, () => new Array(n).fill(0));
for (let i = 0; i < m; i++) {
for (let j = 0; j < k; j++) {
const a = mat1[i][j];
if (a === 0) continue;
for (const [c, v] of rows[j]) res[i][c] += a * v;
}
}
return res;
}Edge cases to test
- 1 x 1 matrices
- A matrix that is entirely zero
- Fully dense matrices (no zeros at all)
- Negative entries that cancel to 0 in the product
- A column vector times a row vector (k = 1), giving a full m x n result
Hints
Hint 1
Write out res[i][c] = sum over j of mat1[i][j] * mat2[j][c]. Which terms of this sum are guaranteed to be 0?
Hint 2
Loop over i, then j, and skip immediately when mat1[i][j] == 0; a non-zero mat1[i][j] adds a scaled copy of row j of mat2 into row i of the result.
Hint 3
Pre-collect the non-zero entries of each row of mat2 so the inner loop touches only those.
FAQ
What is the best time complexity for Sparse Matrix Multiplication?
Optimal (skip zeros with compressed rows) runs in O(m · k + k · n + Z) time and O(k · n) for the compressed rows extra space. Scanning both matrices costs m · k + k · n; Z is the number of non-zero pairs actually multiplied, which is tiny for sparse inputs.
Which pattern does Sparse Matrix Multiplication use?
It is a arrays & hashing problem that uses the matrix traversal pattern. Other problems with the same pattern: Spiral Matrix, Best Meeting Point, Diagonal Traverse.
Is there a brute force solution for Sparse Matrix Multiplication?
Yes. Brute force (textbook triple loop) takes O(m · k · n) time and O(1) extra space. Compute every cell of the result as the dot product of a row of mat1 with a column of mat2, multiplying zeros along with everything else.
Which edge cases should I test for Sparse Matrix Multiplication?
1 x 1 matrices; A matrix that is entirely zero; Fully dense matrices (no zeros at all); Negative entries that cancel to 0 in the product; A column vector times a row vector (k = 1), giving a full m x n result.