⚡Flashcard Drill➔
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

  1. The textbook triple loop is O(m * k * n), but for sparse inputs most entries are zero and contribute nothing.
  2. Precompute, for each row of mat1, the list of (column, value) pairs where the value is non-zero.
  3. For each such pair, add value * mat2[column][j] to res[row][j] for every j.
  4. Skipping zero entries in mat1 is the main saving; you can additionally store mat2 column-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] == 0 implies 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 k dimension: 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.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems