Sparse Matrix Multiplication solution and explanation
Google
9 more videos on this problem
LeetCode 311. Sparse Matrix MultiplicationHappy Coding · 9:59 · 12K views
LeetCode 311 - Sparse Matrix Multiplicationnuravrai2018 · 15:06 · 11K views
Leetcode 311 Sparse Matrix MultiplicationRen Zhang · 31:31 · 10K views
Amazon Coding Interview Question | Leetcode 311 | Sparse Matrix MultiplicationWorkWithGoogler · 17:45 · 4K views
311. Sparse Matrix Multiplication - Week 2/5 Leetcode May ChallengeProgramming Live with Larry · 6:09 · 2K views
LeetCode 311. Sparse Matrix Multiplication| JSer - JavaScript & AlgorithmJSer · 20:10 · 2K views
311. Sparse Matrix Multiplication - Week 5/5 Leetcode April ChallengeProgramming Live with Larry · 9:25 · 679 views
Sparse Matrix Multiplication (Medium), C++, LeetcodeH William Polenz · 38:31 · 658 views
311. Sparse Matrix Multiplication [中文解释]N Z (Padme) · 13:17 · 615 views
leetcode311 Sparse Matrix MultiplicationYinghan Ma (Yinghan) · 11:13 · 597 views
The problem
Given two sparse matrices mat1 of size m x k and mat2 of size k x n, return the result of mat1 x mat2. You may assume that multiplication is always possible.
Example 1:
Input: mat1 = [[1,0,0],[-1,0,3]], mat2 = [[7,0,0],[0,0,0],[0,0,1]] Output: [[7,0,0],[-7,0,3]]
Example 2:
Input: mat1 = [[0]], mat2 = [[0]] Output: [[0]]
Constraints:
m == mat1.lengthk == mat1[i].length == mat2.lengthn == mat2[i].length1 <= m, n, k <= 100-100 <= mat1[i][j], mat2[i][j] <= 100
Approach overview
Problem Overview: You are given two matrices mat1 and mat2. The task is to compute their matrix product. The twist is that the matrices are sparse, meaning most values are zero. A good solution avoids unnecessary multiplications with zero.
Approach 1: Direct Multiplication (O(m * n * p) time, O(1) extra space)
This approach follows the standard matrix multiplication rule. For each cell result[i][j], iterate through index k and compute mat1[i][k] * mat2[k][j]. The key optimization is skipping work when mat1[i][k] == 0, because multiplying by zero contributes nothing to the result. Implementation uses three nested loops over rows of mat1, columns of mat2, and the shared dimension. Even with the zero check, the worst‑case complexity remains O(m * n * p) where m, n, and p are the matrix dimensions. This approach is simple and readable but wastes time when matrices contain many zeros. It mainly relies on basic Array iteration and standard Matrix multiplication rules.
Approach 2: Preprocessing Non‑Zero Values (O(nnz(A) * p) average time, O(nnz(A) + nnz(B)) space)
Sparse matrices benefit from processing only non‑zero entries. First preprocess mat1 and record the column indices and values of non‑zero elements for every row. This structure can be stored using lists or a Hash Table. During multiplication, iterate through the stored non‑zero elements (i, k) from mat1. For each one, multiply it with the corresponding row k in mat2. Since the multiplication happens only when mat1[i][k] is non‑zero, the algorithm skips most useless operations. The runtime becomes proportional to the number of non‑zero values rather than the total matrix size. If nnz(A) is the number of non‑zero entries in mat1, the effective work is roughly O(nnz(A) * p) or better depending on sparsity in mat2. Extra space stores the non‑zero structure, but the speed improvement is significant for large sparse matrices.
Recommended for interviews: Interviewers expect the preprocessing approach. Starting with direct multiplication shows you understand matrix multiplication basics, but recognizing sparsity and skipping zero work demonstrates stronger algorithmic thinking. Mention the idea of storing only non‑zero elements and multiplying selectively. That insight turns a brute force triple loop into a solution that scales with the actual useful data rather than the full matrix size.
Approach 1: Direct Multiplication
We can directly calculate each element in the result matrix according to the definition of matrix multiplication.
The time complexity is O(m times n times k), and the space complexity is O(m times n). Where m and n are the number of rows of matrix mat1 and the number of columns of matrix mat2 respectively, and k is the number of columns of matrix mat1 or the number of rows of matrix mat2.
class Solution:
def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:
m, n = len(mat1), len(mat2[0])
ans = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
for k in range(len(mat2)):
ans[i][j] += mat1[i][k] * mat2[k][j]
return ansclass Solution {
public int[][] multiply(int[][] mat1, int[][] mat2) {
int m = mat1.length, n = mat2[0].length;
int[][] ans = new int[m][n];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
for (int k = 0; k < mat2.length; ++k) {
ans[i][j] += mat1[i][k] * mat2[k][j];
}
}
}
return ans;
}
}class Solution {
public:
vector<vector<int>> multiply(vector<vector<int>>& mat1, vector<vector<int>>& mat2) {
int m = mat1.size(), n = mat2[0].size();
vector<vector<int>> ans(m, vector<int>(n));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
for (int k = 0; k < mat2.size(); ++k) {
ans[i][j] += mat1[i][k] * mat2[k][j];
}
}
}
return ans;
}
};function multiply(mat1: number[][], mat2: number[][]): number[][] {
const [m, n] = [mat1.length, mat2[0].length];
const ans: number[][] = Array.from({ length: m }, () => Array.from({ length: n }, () => 0));
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
for (let k = 0; k < mat2.length; ++k) {
ans[i][j] += mat1[i][k] * mat2[k][j];
}
}
}
return ans;
}func multiply(mat1 [][]int, mat2 [][]int) [][]int {
m, n := len(mat1), len(mat2[0])
ans := make([][]int, m)
for i := range ans {
ans[i] = make([]int, n)
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
for k := 0; k < len(mat2); k++ {
ans[i][j] += mat1[i][k] * mat2[k][j]
}
}
}
return ans
}Approach 2: Preprocessing
We can preprocess the sparse representation of the two matrices, i.e., g1[i] represents the column index and value of all non-zero elements in the ith row of matrix mat1, and g2[i] represents the column index and value of all non-zero elements in the ith row of matrix mat2.
Next, we traverse each row i, traverse each element (k, x) in g1[i], traverse each element (j, y) in g2[k], then mat1[i][k] times mat2[k][j] will correspond to ans[i][j] in the result matrix, and we can accumulate all the results.
The time complexity is O(m times n times k), and the space complexity is O(m times n). Where m and n are the number of rows of matrix mat1 and the number of columns of matrix mat2 respectively, and k is the number of columns of matrix mat1 or the number of rows of matrix mat2.
class Solution:
def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:
def f(mat: List[List[int]]) -> List[List[int]]:
g = [[] for _ in range(len(mat))]
for i, row in enumerate(mat):
for j, x in enumerate(row):
if x:
g[i].append((j, x))
return g
g1 = f(mat1)
g2 = f(mat2)
m, n = len(mat1), len(mat2[0])
ans = [[0] * n for _ in range(m)]
for i in range(m):
for k, x in g1[i]:
for j, y in g2[k]:
ans[i][j] += x * y
return ansclass Solution {
public int[][] multiply(int[][] mat1, int[][] mat2) {
int m = mat1.length, n = mat2[0].length;
int[][] ans = new int[m][n];
var g1 = f(mat1);
var g2 = f(mat2);
for (int i = 0; i < m; ++i) {
for (int[] p : g1[i]) {
int k = p[0], x = p[1];
for (int[] q : g2[k]) {
int j = q[0], y = q[1];
ans[i][j] += x * y;
}
}
}
return ans;
}
private List<int[]>[] f(int[][] mat) {
int m = mat.length, n = mat[0].length;
List<int[]>[] g = new List[m];
Arrays.setAll(g, i -> new ArrayList<>());
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (mat[i][j] != 0) {
g[i].add(new int[] {j, mat[i][j]});
}
}
}
return g;
}
}class Solution {
public:
vector<vector<int>> multiply(vector<vector<int>>& mat1, vector<vector<int>>& mat2) {
int m = mat1.size(), n = mat2[0].size();
vector<vector<int>> ans(m, vector<int>(n));
auto g1 = f(mat1), g2 = f(mat2);
for (int i = 0; i < m; ++i) {
for (auto& [k, x] : g1[i]) {
for (auto& [j, y] : g2[k]) {
ans[i][j] += x * y;
}
}
}
return ans;
}
vector<vector<pair<int, int>>> f(vector<vector<int>>& mat) {
int m = mat.size(), n = mat[0].size();
vector<vector<pair<int, int>>> g(m);
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (mat[i][j]) {
g[i].emplace_back(j, mat[i][j]);
}
}
}
return g;
}
};function multiply(mat1: number[][], mat2: number[][]): number[][] {
const [m, n] = [mat1.length, mat2[0].length];
const ans: number[][] = Array.from({ length: m }, () => Array.from({ length: n }, () => 0));
const f = (mat: number[][]): number[][][] => {
const [m, n] = [mat.length, mat[0].length];
const ans: number[][][] = Array.from({ length: m }, () => []);
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
if (mat[i][j] !== 0) {
ans[i].push([j, mat[i][j]]);
}
}
}
return ans;
};
const g1 = f(mat1);
const g2 = f(mat2);
for (let i = 0; i < m; ++i) {
for (const [k, x] of g1[i]) {
for (const [j, y] of g2[k]) {
ans[i][j] += x * y;
}
}
}
return ans;
}func multiply(mat1 [][]int, mat2 [][]int) [][]int {
m, n := len(mat1), len(mat2[0])
ans := make([][]int, m)
for i := range ans {
ans[i] = make([]int, n)
}
f := func(mat [][]int) [][][2]int {
m, n := len(mat), len(mat[0])
g := make([][][2]int, m)
for i := range g {
g[i] = make([][2]int, 0, n)
for j := range mat[i] {
if mat[i][j] != 0 {
g[i] = append(g[i], [2]int{j, mat[i][j]})
}
}
}
return g
}
g1, g2 := f(mat1), f(mat2)
for i := range g1 {
for _, p := range g1[i] {
k, x := p[0], p[1]
for _, q := range g2[k] {
j, y := q[0], q[1]
ans[i][j] += x * y
}
}
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Direct Multiplication | – |
| Preprocessing | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Multiplication | O(m * n * p) | O(1) | Small matrices or when sparsity is low and implementation simplicity matters |
| Direct Multiplication with Zero Skip | O(m * n * p) worst case | O(1) | Slight optimization when many values in the first matrix are zero |
| Preprocessing Non‑Zero Values | ~O(nnz(A) * p) | O(nnz(A) + nnz(B)) | Large sparse matrices where skipping zero operations drastically reduces work |
Frequently asked questions
Is Sparse Matrix Multiplication easy or hard?
The problem is considered medium difficulty. The basic matrix multiplication idea is straightforward, but recognizing that sparse matrices allow skipping zero operations is the key insight. Implementing the optimized approach requires careful iteration over non‑zero elements.
Sparse Matrix Multiplication Python/Java solution
Implementations usually preprocess rows of the first matrix and then multiply only non‑zero entries. Python often uses lists of pairs or dictionaries, while Java uses ArrayList or HashMap structures. The same logic works in C++, Go, and TypeScript with language‑specific containers.
How to solve Sparse Matrix Multiplication in O(n)?
Strict O(n) time is usually not possible for general matrix multiplication because each non‑zero element may affect multiple outputs. Practical sparse solutions run in time proportional to the number of non‑zero entries, often written as O(nnz). By preprocessing non‑zero values and skipping zeros, the algorithm avoids scanning the entire matrix.
What is the best approach for Sparse Matrix Multiplication?
The preprocessing approach that stores only non‑zero elements is the most efficient for sparse matrices. Instead of multiplying every cell, the algorithm iterates through non‑zero entries in the first matrix and multiplies them with relevant rows in the second matrix. This reduces unnecessary operations and makes the runtime depend on the number of non‑zero values rather than total matrix size.
Is Sparse Matrix Multiplication asked at Google/Amazon/Meta?
Sparse matrix problems appear in interviews at companies working with large‑scale data or graphics systems. Variants of this problem have been reported in interviews at companies like Google and Meta. The goal is to test understanding of matrix multiplication plus optimization using sparsity.
What data structure is used in Sparse Matrix Multiplication?
Efficient solutions typically store non‑zero entries using lists or hash maps. A common structure maps each row index to the column indices and values that are non‑zero. This allows the algorithm to iterate only over meaningful elements during multiplication.
What is the time complexity of Sparse Matrix Multiplication?
The naive matrix multiplication algorithm runs in O(m * n * p) time where m, n, and p are matrix dimensions. With sparse optimization, the runtime becomes closer to O(nnz(A) * p) or proportional to the number of non‑zero entries. This improvement is significant when the matrix contains mostly zeros.