LeetCode 311 - Sparse Matrix Multiplication

This problem asks us to multiply two matrices, but with an important detail: both matrices are sparse. A sparse matrix is a matrix where most entries are zero. The goal is to take advantage of this property so that we avoid unnecessary computation involving zero values.

leetcodemediumarrayhash-tablematrix

LeetCode Problem 311

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Matrix

Solution

Problem Understanding

This problem asks us to multiply two matrices, but with an important detail: both matrices are sparse. A sparse matrix is a matrix where most entries are zero. The goal is to take advantage of this property so that we avoid unnecessary computation involving zero values.

We are given:

  • mat1, an m x k matrix
  • mat2, a k x n matrix

Because the number of columns in mat1 matches the number of rows in mat2, matrix multiplication is valid.

The result matrix will have dimensions m x n.

Recall how matrix multiplication works. For every cell (i, j) in the result matrix:

$$result[i][j] = \sum_{x=0}^{k-1} mat1[i][x] \times mat2[x][j]$$

This means each output cell is computed by taking the dot product of:

  • row i from mat1
  • column j from mat2

The constraints are relatively small, since each dimension is at most 100. A straightforward solution is therefore technically acceptable. However, the problem specifically focuses on sparse matrices, which means the intended optimization is to skip operations involving zeros.

This matters because multiplying by zero contributes nothing to the final answer. If a large percentage of matrix entries are zero, then most multiplication operations in the brute-force solution are wasted work.

Several edge cases are important:

  • Entire rows or columns may contain only zeros.
  • One or both matrices may consist entirely of zeros.
  • Negative values are allowed, so we cannot make assumptions about positivity.
  • Matrices may be rectangular, not necessarily square.
  • Multiple non-zero entries may contribute to the same result cell.

The problem guarantees that dimensions are always compatible for multiplication, so we never need to validate matrix sizes.

Approaches

Brute Force Approach

The most direct solution is standard matrix multiplication.

For every row i in mat1 and every column j in mat2, we iterate through all intermediate indices x from 0 to k - 1 and compute:

$$result[i][j] += mat1[i][x] \times mat2[x][j]$$

This approach is correct because it directly implements the mathematical definition of matrix multiplication.

However, it performs many unnecessary operations when matrices are sparse. Even if mat1[i][x] or mat2[x][j] is zero, the multiplication is still executed despite contributing nothing.

The total work is:

$$O(m \times k \times n)$$

For dense matrices this is unavoidable, but for sparse matrices we can do better by skipping zero values.

Optimal Sparse Matrix Approach

The key observation is that multiplication by zero has no effect.

Instead of iterating over every possible combination, we only process non-zero values.

Suppose mat1[i][k] is non-zero. Only then is it worth examining row k of mat2, because:

$$mat1[i][k] \times mat2[k][j]$$

can contribute to the result.

If mat2[k][j] is also non-zero, then we update:

$$result[i][j] += mat1[i][k] \times mat2[k][j]$$

This avoids unnecessary operations involving zeros.

The optimization becomes especially powerful when matrices contain very few non-zero entries.

Approach Time Complexity Space Complexity Notes
Brute Force O(m × k × n) O(m × n) Computes every possible multiplication
Optimal O(non-zero operations) O(m × n) Skips zero entries to reduce work

The exact runtime of the optimal solution depends on how many non-zero values exist.

Algorithm Walkthrough

  1. Determine the dimensions of the matrices.

Let:

  • m = number of rows in mat1
  • k = number of columns in mat1
  • n = number of columns in mat2

The result matrix will have dimensions m x n. 2. Initialize the result matrix with zeros.

Every position initially contains 0 because no products have been accumulated yet. 3. Iterate through each row i of mat1.

We process contributions from one row at a time. 4. For each column index x in mat1[i], check whether mat1[i][x] is non-zero.

If the value is zero, skip it entirely because it contributes nothing to any result cell. 5. When a non-zero value is found in mat1[i][x], iterate through row x of mat2.

This works because matrix multiplication pairs:

  • mat1[i][x]
  • mat2[x][j]
  1. For every column j in mat2[x], check whether mat2[x][j] is non-zero.

Again, zero values contribute nothing and can be skipped. 7. Update the result matrix.

Add:

$$mat1[i][x] \times mat2[x][j]$$

to:

$$result[i][j]$$ 8. Continue until all rows and relevant non-zero entries are processed. 9. Return the completed result matrix.

Why it works

Matrix multiplication is defined as the sum of pairwise products across shared dimensions. The optimized algorithm still computes exactly the same products as the brute-force solution, but it skips products involving zeros because those terms always evaluate to zero and do not affect the final sum.

Therefore, every meaningful contribution is preserved, and the final matrix is correct.

Python Solution

from typing import List

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

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

        for i in range(m):
            for x in range(k):
                if mat1[i][x] != 0:
                    for j in range(n):
                        if mat2[x][j] != 0:
                            result[i][j] += mat1[i][x] * mat2[x][j]

        return result

The implementation begins by extracting the matrix dimensions. This allows us to correctly size the result matrix.

The result matrix is initialized with zeros because matrix multiplication accumulates sums into each cell.

The outer loop iterates through rows of mat1. The second loop iterates through columns of that row, which correspond to rows in mat2.

Before performing any multiplication, the code checks whether mat1[i][x] is non-zero. If it is zero, all products involving that value would also be zero, so the algorithm skips the entire inner computation.

If the value is non-zero, we iterate across the corresponding row in mat2. Another zero check avoids unnecessary multiplications involving mat2[x][j].

Whenever both values are non-zero, their product contributes to the result matrix.

The final matrix is returned after all contributions are accumulated.

Go Solution

func multiply(mat1 [][]int, mat2 [][]int) [][]int {
    m := len(mat1)
    k := len(mat1[0])
    n := len(mat2[0])

    result := make([][]int, m)

    for i := 0; i < m; i++ {
        result[i] = make([]int, n)
    }

    for i := 0; i < m; i++ {
        for x := 0; x < k; x++ {
            if mat1[i][x] != 0 {
                for j := 0; j < n; j++ {
                    if mat2[x][j] != 0 {
                        result[i][j] += mat1[i][x] * mat2[x][j]
                    }
                }
            }
        }
    }

    return result
}

The Go implementation follows the same algorithmic structure as the Python version.

The primary difference is matrix initialization. In Go, slices must be explicitly allocated using make.

Go integers are sufficient for the problem constraints because values remain well within 32-bit integer limits.

Both implementations avoid unnecessary multiplication involving zeros, preserving the sparse optimization.

Worked Examples

Example 1

Input:

mat1 = [
  [1,0,0],
  [-1,0,3]
]

mat2 = [
  [7,0,0],
  [0,0,0],
  [0,0,1]
]

Initial result matrix:

[
  [0,0,0],
  [0,0,0]
]

Processing Row 0 of mat1

i x mat1[i][x] Action
0 0 1 Non-zero, process row 0 of mat2
0 1 0 Skip
0 2 0 Skip

Now process row 0 of mat2:

j mat2[0][j] Update
0 7 result[0][0] += 1 × 7 = 7
1 0 Skip
2 0 Skip

Result becomes:

[
  [7,0,0],
  [0,0,0]
]

Processing Row 1 of mat1

i x mat1[i][x] Action
1 0 -1 Process row 0 of mat2
1 1 0 Skip
1 2 3 Process row 2 of mat2

Processing x = 0:

j mat2[0][j] Update
0 7 result[1][0] += -1 × 7 = -7
1 0 Skip
2 0 Skip

Result:

[
  [7,0,0],
  [-7,0,0]
]

Processing x = 2:

j mat2[2][j] Update
0 0 Skip
1 0 Skip
2 1 result[1][2] += 3 × 1 = 3

Final result:

[
  [7,0,0],
  [-7,0,3]
]

Example 2

Input:

mat1 = [[0]]
mat2 = [[0]]

The single value in mat1 is zero, so the algorithm skips all multiplication work.

Final result:

[[0]]

Complexity Analysis

Measure Complexity Explanation
Time O(m × k × n) worst case Every value may be non-zero in dense matrices
Space O(m × n) Required for the result matrix

In the worst case, when matrices are dense, the optimized algorithm performs the same amount of work as standard matrix multiplication.

However, for sparse matrices the practical runtime is much better because many operations are skipped. The algorithm only performs multiplications when both contributing values are non-zero.

The space complexity comes entirely from storing the output matrix.

Test Cases

from typing import List

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

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

        for i in range(m):
            for x in range(k):
                if mat1[i][x] != 0:
                    for j in range(n):
                        if mat2[x][j] != 0:
                            result[i][j] += mat1[i][x] * mat2[x][j]

        return result

sol = Solution()

# Provided example with sparse matrices
assert sol.multiply(
    [[1, 0, 0], [-1, 0, 3]],
    [[7, 0, 0], [0, 0, 0], [0, 0, 1]]
) == [[7, 0, 0], [-7, 0, 3]]

# Single zero element matrices
assert sol.multiply([[0]], [[0]]) == [[0]]

# Dense matrices
assert sol.multiply(
    [[1, 2], [3, 4]],
    [[5, 6], [7, 8]]
) == [[19, 22], [43, 50]]

# Matrix with entire zero row
assert sol.multiply(
    [[0, 0], [1, 2]],
    [[3, 4], [5, 6]]
) == [[0, 0], [13, 16]]

# Matrix with entire zero column contribution
assert sol.multiply(
    [[1, 0]],
    [[0, 5], [0, 0]]
) == [[0, 5]]

# Negative values
assert sol.multiply(
    [[-1, 2]],
    [[3], [-4]]
) == [[-11]]

# Rectangular matrices
assert sol.multiply(
    [[1, 2, 3]],
    [[1], [2], [3]]
) == [[14]]

# All zeros larger matrix
assert sol.multiply(
    [[0, 0], [0, 0]],
    [[0, 0], [0, 0]]
) == [[0, 0], [0, 0]]

# Multiple contributions to same cell
assert sol.multiply(
    [[1, 1]],
    [[2], [3]]
) == [[5]]
Test Why
Example 1 Validates sparse optimization with mixed zeros
Example 2 Validates smallest possible input
Dense matrices Confirms correctness when no sparsity exists
Entire zero row Ensures skipped computations work correctly
Zero column contribution Tests partial sparsity
Negative values Verifies sign handling
Rectangular matrices Confirms non-square matrix support
All zeros Ensures completely sparse input works
Multiple contributions Verifies accumulation logic

Edge Cases

Completely Sparse Matrices

A matrix may contain only zeros. In this situation, every multiplication would produce zero, so the final matrix should also contain only zeros.

This can easily produce bugs if the implementation assumes every row contributes values. The optimized solution handles this naturally because it skips all entries where mat1[i][x] == 0.

Rectangular Matrices

The matrices are not guaranteed to be square. For example, a 1 x 3 matrix may be multiplied by a 3 x 2 matrix.

A common mistake is assuming equal dimensions everywhere. The implementation correctly extracts:

  • rows from mat1
  • columns from mat2
  • shared dimension k

This ensures all rectangular configurations work properly.

Multiple Contributions to the Same Cell

A single result cell may receive contributions from multiple intermediate indices.

For example:

$$result[i][j] = mat1[i][0] \times mat2[0][j] + mat1[i][1] \times mat2[1][j]$$

A buggy implementation might overwrite values instead of accumulating them. The solution correctly uses += so every contribution is included.