Practice/Meta/Leetcode 311. Sparse Matrix Multiplication

Leetcode 311. Sparse Matrix Multiplication

CodingOptional

Problem

You are given two matrices A (of dimensions m × k) and B (of dimensions k × n). Your task is to compute their product C = A × B, where C will have dimensions m × n.

Both input matrices are sparse, meaning most of their elements are zero. A naive matrix multiplication algorithm that processes every element would have O(m × k × n) time complexity, performing many unnecessary multiplications and additions involving zeros.

Your goal is to implement an optimized multiplication algorithm that takes advantage of the sparsity by only processing non-zero elements, thereby improving performance when the matrices contain many zeros.

Requirements

1. Implement a function that correctly computes the matrix product C = A × B
2. Optimize for sparse matrices by avoiding operations on zero elements
3. Return the result as a 2D array with the same structure as a standard matrix
4. Handle edge cases including matrices with all zeros or no zeros

Constraints

• 1 ≤ m, k, n ≤ 100
• -100 ≤ matrixA[i][j], matrixB[i][j] ≤ 100
• The number of non-zero elements is at most 100
• matrixA has dimensions m × k
• matrixB has dimensions k × n

Examples

Example 1:

Input: matrixA = [[1, 0, 0], [0, 0, 2]] matrixB = [[0, 3], [4, 0], [0, 5]] Output: [[0, 3], [0, 10]] Explanation: Row 0 of A: [1,0,0] × columns of B → [1*0, 1*3] = [0, 3] Row 1 of A: [0,0,2] × columns of B → [2*0, 2*5] = [0, 10]

Example 2:

Input: matrixA = [[1, -5]] matrixB = [[12], [-1]] Output: [[17]] Explanation: Single row times single column: 1*12 + (-5)*(-1) = 12 + 5 = 17

Example 3:

Input: matrixA = [[0, 1], [1, 0]] matrixB = [[1, 0], [0, 1]] Output: [[0, 1], [1, 0]] Explanation: Identity-like matrices produce predictable outputs