LeetCode 311: Sparse Matrix Multiplication Solution in Python – A Step-by-Step Guide

What Is LeetCode 311: Sparse Matrix Multiplication?

In LeetCode 311: Sparse Matrix Multiplication, you’re given two matrices, mat1 (m x k) and mat2 (k x n), and need to compute their product, a new matrix of size m x n. The catch? These matrices are sparse, meaning most elements are zero, so a naive approach wastes effort. For example, multiplying [[1,0,0],[0,1,0]] by [[1,0],[0,1],[0,0]] should be quick if we focus only on non-zero elements. This problem tests your ability to optimize a classic algorithm for real-world efficiency.

Problem Statement

• Input: Two 2D integer arrays mat1 (m x k) and mat2 (k x n).
• Output: A 2D integer array—the product mat1 * mat2 (m x n).
• Rules:
• Matrix multiplication rules apply: mat1[i][j] dots mat2[j][k] for each result cell.
• Matrices are sparse (many zeros).

Constraints

• 1 <= m, n, k <= 100
• -100 <= mat1[i][j], mat2[i][j] <= 100

Examples

• 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]]
• Input: mat1 = [[1,0],[0,1]], mat2 = [[1,0],[0,1]]
• Output: [[1,0],[0,1]]
• Input: mat1 = [[1,0,0]], mat2 = [[1],[0],[0]]
• Output: [[1]]

Understanding the Problem: Multiplying Sparse Matrices

To solve LeetCode 311: Sparse Matrix Multiplication in Python, we need a function that multiplies two matrices efficiently, leveraging their sparsity. Standard matrix multiplication takes O(mnk) time, computing every dot product—even for zeros. Since these matrices are sparse, we can do better:

• Best Solution (Sparse-Aware): O(m * k + n * k + non-zero operations) time, O(m*n) space—skips zeros.
• Alternative Solution (Standard): O(m*n*k) time, O(m*n) space—brute force.

Let’s start with the sparse-aware solution, explained in a way that’s easy to follow.

Best Solution: Sparse-Aware Multiplication

Why This Is the Best Solution

The sparse-aware approach is the top choice for LeetCode 311 because it’s optimized for sparsity—running in time proportional to non-zero elements rather than the full O(mnk). It preprocesses the matrices to store only non-zero values, then computes the result using these, avoiding unnecessary multiplications. It’s like focusing only on the landmarks in a sparse map—efficient and practical!

How It Works

Think of this as a smart multiplication:

• Step 1: Preprocess Non-Zeros:
• For mat1, store (row, col, value) for non-zero elements.
• For mat2, store (row, col, value) or use column-wise access.
• Step 2: Compute Result:
• For each result cell (i, j), multiply and sum only non-zero pairs from mat1 row i and mat2 col j.
• Step 3: Why It Works:
• Skips zero multiplications, reducing operations.
• Still produces the correct m x n result.

It’s like a targeted dot product—only the essentials!

Step-by-Step Example

Example: mat1 = [[1,0,0],[-1,0,3]], mat2 = [[7,0,0],[0,0,0],[0,0,1]]

• Sparse mat1: [(0,0,1), (1,0,-1), (1,2,3)]
• Sparse mat2: [(0,0,7), (2,2,1)]
• Result (2x3):
• (0,0): 1*7 = 7
• (0,1): 0 (no pairs)
• (0,2): 0 (no pairs)
• (1,0): -1*7 = -7
• (1,1): 0
• (1,2): 3*1 = 3
• Output: [[7,0,0],[-7,0,3]]

Code with Detailed Line-by-Line Explanation

Copy codeclass Solution:
    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:
        m, k, n = len(mat1), len(mat1[0]), len(mat2[0])

        # Store non-zero elements of mat1
        sparse1 = []
        for i in range(m):
            for j in range(k):
                if mat1[i][j] != 0:
                    sparse1.append((i, j, mat1[i][j]))

        # Initialize result matrix
        result = [[0] * n for _ in range(m)]

        # Multiply using non-zero elements
        for i, j, val1 in sparse1:
            for col in range(n):
                if mat2[j][col] != 0:  # Only multiply with non-zero mat2 elements
                    result[i][col] += val1 * mat2[j][col]

        return result

• Line 3: Get dimensions: m (rows mat1), k (cols mat1/rows mat2), n (cols mat2).
• Lines 5-9: Build sparse list for mat1—(row, col, value).
• Line 11: Initialize m x n result with zeros.
• Lines 14-17: Compute:
• For each non-zero in mat1, check mat2’s column.
• Add product to result if mat2 value is non-zero.
• Time Complexity: O(m*k + n*k + non-zero operations)—depends on sparsity.
• Space Complexity: O(m*n + non-zeros in mat1)—result plus sparse storage.

This is like a sparse matrix wizard—fast and focused!

Alternative Solution: Standard Matrix Multiplication

Why an Alternative Approach?

The standard approach uses the classic matrix multiplication algorithm—O(mnk) time, O(m*n) space. It’s simpler to understand and works regardless of sparsity, making it a good baseline. It’s like multiplying every cell the old-fashioned way—reliable but not optimized for zeros.

How It Works

Follow the textbook method:

• Step 1: Initialize result matrix.
• Step 2: For each (i, j) in result:
• Compute dot product of mat1 row i and mat2 col j.
• Step 3: Fill result.

Step-by-Step Example

Example: mat1 = [[1,0],[0,1]], mat2 = [[1,0],[0,1]]

• Result (2x2):
• (0,0): 1*1 + 0*0 = 1
• (0,1): 1*0 + 0*1 = 0
• (1,0): 0*1 + 1*0 = 0
• (1,1): 0*0 + 1*1 = 1
• Output: [[1,0],[0,1]]

Code for Standard Approach

Copy codeclass Solution:
    def multiply(self, mat1: List[List[int]], mat2: personallyList[int]]) -> List[List[int]]:
        m, k, n = len(mat1), len(mat1[0]), len(mat2[0])
        result = [[0] * n for _ in range(m)]

        for i in range(m):
            for j in range(n):
                for p in range(k):
                    result[i][j] += mat1[i][p] * mat2[p][j]

        return result

• Time Complexity: O(m*n*k)—every element processed.
• Space Complexity: O(m*n)—result matrix.

It’s a full matrix cruncher—steady but slow!

Comparing the Two Solutions

• Sparse-Aware (Best):
• Pros: Faster for sparse matrices, O(m*k + n*k + non-zero ops).
• Cons: Slightly more complex.
• Standard (Alternative):
• Pros: O(m*n*k), simple and universal.
• Cons: Inefficient for sparse inputs.

Sparse-aware wins for this problem.

Additional Examples and Edge Cases

• [[0]], [[1]]: [[0]].
• [[1,0],[0,0]], [[0,1],[1,0]]: [[0,1],[0,0]].
• [[-1]], [[2]]: [[-2]].

Both handle these correctly.

Complexity Breakdown

• Sparse-Aware: Time O(m*k + n*k + non-zero ops), Space O(m*n + non-zeros).
• Standard: Time O(m*n*k), Space O(m*n).

Sparse-aware shines with sparsity.

Key Takeaways

• Sparse-Aware: Skip zeros—smart and fast!
• Standard: Full sweep—clear and classic!
• Python: Lists and loops rock—see [Python Basics](/python/basics).
• Matrices: Sparsity changes the game.

Final Thoughts: Multiply Efficiently

LeetCode 311: Sparse Matrix Multiplication in Python is a practical optimization challenge. The sparse-aware solution leverages sparsity for speed, while the standard method offers simplicity. Want more matrix fun? Try LeetCode 48: Rotate Image or LeetCode 73: Set Matrix Zeroes. Ready to multiply? Head to Solve LeetCode 311 on LeetCode and crunch those matrices today!