Domain 2MediumCORE

Sparse Matrix Multiplication

We are given two matrices: mat1 of dimensions $m times k$ and mat2 of dimensions $k times n$. We need to compute their product matrix $C = mat1 times mat2$, which will have dimensions $m times n$. The core mathematical operation is the dot product of rows from mat1 with columns from mat2.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Hash Table

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 m×km \times k and mat2 of dimensions k×nk \times n. We need to compute their product matrix C=mat1×mat2C = mat1 \times mat2, which will have dimensions m×nm \times n. 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 O(m⋅n⋅k)O(m \cdot n \cdot k) 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 (val=0val = 0).
  • 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 kk of mat1 matches the outer dimension of mat2.

Intuition

A brute-force approach involves three nested loops: iterate over rows of A (ii), columns of B (jj), and summing across shared index kk. This is O(m⋅n⋅k)O(m \cdot n \cdot k). 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.

  1. Optimization on A: Iterate through rows of mat1. For each row, iterate columns kk. If mat1[i][k] == 0, skip it entirely for that specific term in the dot product sum.
  2. Optimization on B: When we access a non-zero element from A at column index kk, we need to multiply by elements of Row kk in mat2. If an element in mat2 is zero, its contribution is also null. We can skip adding it or simply check before multiplying.
  3. 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

  1. Initialize Result Matrix: Create an m×nm \times n matrix filled with zeros (res). This is necessary because every cell in the result starts at 0 and accumulates dot products.
  2. Iterate Rows of mat1: Loop through each row index i. Access the current row vector from A.
  3. Filter Non-Zeros in Row AA: 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].
  4. Iterate Columns of Result / Rows of mat2: For the specific column index kk identified above, access Row kk from Matrix B (mat2[k]). Iterate through columns j (0 to n-1).
    • If val_b = mat2[col_idx][j] is non-zero: Add (val_a * val_b) to res[i][j].
  5. 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 Nnz_AN_{nz\_A} be the number of non-zero elements in mat1. The complexity is roughly proportional to ∑(non-zeros in A)×(avg non-zeros in corresponding row of B)\sum (\text{non-zeros in A}) \times (\text{avg non-zeros in corresponding row of B}). In the worst case (dense matrix), this degrades to standard O(m⋅n⋅k)O(m \cdot n \cdot k). Given constraints (N=100N=100), even dense multiplication is roughly 10610^6 operations, which fits well within time limits.
  • Space Complexity: O(m×n)O(m \times n) to store the result matrix. We do not use extra space for sparse structures in this implementation, keeping auxiliary space minimal (O(1)O(1) 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 m,n,k≥1m, n, k \ge 1, 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 == 0 check skips everything immediately; result remains zeros matrix (correct behavior).