NeetCode #24LC-311MediumArrays & HashingNC Algo100
← Back to All Problems#24 · #311 · Sparse Matrix Multiplication(稀疏矩阵的乘法)
📌 Problem Statement & Constraints
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 the multiplication is always possible. Constraints: 1 <= m, k, n <= 100, -100 <= mat1[i][j], mat2[i][j] <= 100.💡 Core Algorithmic Approaches
- The textbook triple loop is O(m * k * n), but for sparse inputs most entries are zero and contribute nothing.
- Precompute, for each row of
mat1, the list of(column, value)pairs where the value is non-zero. - For each such pair, add
value * mat2[column][j]tores[row][j]for everyj. - Skipping zero entries in
mat1is the main saving; you can additionally storemat2column-wise to skip its zeros.
💻 Benchmark Python3 Implementation
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)]
# index the non-zero entries of mat1 row by row
nz1 = [[(t, v) for t, v in enumerate(mat1[i]) if v] for i in range(m)]
for i in range(m):
for t, v in nz1[i]: # only non-zero terms contribute
row2 = mat2[t]
for j in range(n):
if row2[j]:
res[i][j] += v * row2[j]
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(m * k * n) worst case, but proportional to the number of non-zero entries in practice: for each non-zero of mat1 we touch one row of mat2.
💾 Space Complexity
O(m + nnz(mat1)) for the non-zero index, plus O(m * n) for the output.
⚠️ Interview Pitfalls & Follow-ups
- Writing the naive triple loop without skipping zeros: correct but wasteful for the sparse inputs the problem targets.
- Assuming
mat1[i][j] == 0implies the whole product row is zero: only that single term vanishes; other terms still contribute. - Reusing the input matrix for the output: the shapes differ whenever
n != k. - Forgetting the
kdimension: it is the shared inner dimension and must be iterated in the accumulation.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.