311. Sparse Matrix Multiplication
Model: qwen3.5:9b
Topics: Hash Table
FAANG asked: 1
Acceptance rate: 64.1%
Problem Breakdown
We are given two matrices: mat1 of dimensions and mat2 of dimensions . We need to compute their product matrix , which will have dimensions . The core mathematical operation is the dot product of rows from mat1 with columns from mat2.
Key Constraints & Edge Cases:
- Dimensions: All lengths are between 1 and 100. This means we don’t need to worry about massive memory allocation, but brute force might be slow if the matrices were dense (though for these constraints it passes). The problem title “Sparse Matrix” implies most elements are zero ().
- Sparsity: Multiplying by zero yields no contribution to the sum. Iterating over zeros is wasted CPU cycles and memory bandwidth usage. We must optimize our loops to skip these cases.
- Values: Integers between -100 and 100. No overflow issues in Python, but we should handle negative numbers correctly (standard arithmetic).
- Implicit Constraint: The inner dimension of
mat1matches the outer dimension ofmat2.
Intuition
A brute-force approach involves three nested loops: iterate over rows of A (), columns of B (), and summing across shared index . This is . If matrices are dense, this works. However, if they are sparse (mostly zeros), we perform useless multiplications like 0 * x or additions to zero in the result matrix.
The Insight: We should only process non-zero elements.
- Optimization on A: Iterate through rows of
mat1. For each row, iterate columns . Ifmat1[i][k] == 0, skip it entirely for that specific term in the dot product sum. - Optimization on B: When we access a non-zero element from A at column index , we need to multiply by elements of Row in
mat2. If an element inmat2is zero, its contribution is also null. We can skip adding it or simply check before multiplying. - Result Initialization: Initialize the result matrix with zeros so that additions work correctly (accumulating sums).
By filtering out non-zero elements from A first and checking B’s sparsity during multiplication, we reduce complexity to be proportional to the number of non-zero entries rather than total cells.
Approach
- Initialize Result Matrix: Create an matrix filled with zeros (
res). This is necessary because every cell in the result starts at 0 and accumulates dot products. - Iterate Rows of
mat1: Loop through each row indexi. Access the current row vector from A. - Filter Non-Zeros in Row : Iterate over columns (which corresponds to rows in B). If
mat1[i][col_idx]is non-zero:- Retrieve value
val_a = mat1[i][col_idx].
- Retrieve value
- Iterate Columns of Result / Rows of
mat2: For the specific column index identified above, access Row from Matrix B (mat2[k]). Iterate through columnsj(0 to n-1).- If
val_b = mat2[col_idx][j]is non-zero: Add(val_a * val_b)tores[i][j].
- If
- Return Result: Return the accumulated matrix.
This approach ensures we only perform arithmetic operations when they contribute a value, significantly speeding up execution on sparse inputs compared to dense multiplication logic.
Complexity Analysis
- Time Complexity:
- Let be the number of non-zero elements in
mat1. The complexity is roughly proportional to . In the worst case (dense matrix), this degrades to standard . Given constraints (), even dense multiplication is roughly operations, which fits well within time limits.
- Let be the number of non-zero elements in
- Space Complexity: to store the result matrix. We do not use extra space for sparse structures in this implementation, keeping auxiliary space minimal ( beyond output).
Solution
class Solution:
def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:
m = len(mat1) # Rows of A (Result rows)
k_dim = len(mat1[0])# Cols of A / Rows of B
n = len(mat2[0]) # Cols of B (Result cols)
# Initialize result matrix with zeros
res = [[0] * n for _ in range(m)]
# Iterate over each row i of mat1
for i in range(m):
row_a = mat1[i]
# Optimization: Only iterate columns where A has a non-zero value.
# We use 'col_idx' to avoid shadowing the dimension variable if needed,
# though here it's local scope logic. This corresponds to rows of B.
for col_idx, val_a in enumerate(row_a):
if val_a == 0:
continue
# If A is sparse here (val_a != 0), we need to multiply by the corresponding row from B.
# The column index 'col_idx' corresponds to a specific Row 'col_idx' in mat2.
row_b = mat2[col_idx]
for j, val_b in enumerate(row_b):
if val_b == 0: continue
res[i][j] += val_a * val_b
return res
Edge Cases Handled
- Empty Matrices: Constraints state , so empty matrices are not possible per problem definition. However, the logic handles single-element matrices correctly (loops run once).
- Single Element Rows/Cols: The loops handle dimensions of size 1 without index errors (
range(1)works as expected). - Negative Numbers: Python’s integer arithmetic naturally handles negative values in multiplication and addition without overflow issues for the given constraints.
- Zero Matrices: If all elements are zero,
val_a == 0check skips everything immediately; result remains zeros matrix (correct behavior).