How do you solve Sparse Matrix Multiplication?

Iterate over each row of mat1 and each element in that row. If the element is zero, skip to the next. Otherwise, iterate over the corresponding row in mat2 (which corresponds to the column in the result matrix) and multiply only if the mat2 element is non-zero. Accumulate the product into the result matrix. This approach preserves correctness while optimizing performance for sparse inputs.

What pattern does Sparse Matrix Multiplication use?

The Pattern: Matrix Traversal (Sparse Optimization) The Heuristic: When multiplying matrices, skip computations involving zero elements to reduce unnecessary operations, especially effective for sparse matrices where many elements are zero.

Sparse Matrix Multiplication | Matrix Traversal

Q: What is the time complexity of Sparse Matrix Multiplication?

O(rows1 * cols1 * cols2). In the worst case, the algorithm visits every element in mat1 and mat2 relevant to the multiplication, resulting in cubic time relative to matrix dimensions. However, skipping zero elements reduces the actual operations for sparse matrices.

Problem

Given two matrices mat1 and mat2, return the product of mat1 and mat2 as a new matrix.

1 ≤ mat1.length, mat1[0].length, mat2.length, mat2[0].length ≤ 100
−100 ≤ mat1[i][j], mat2[i][j] ≤ 100
mat1[0].length == mat2.length

Example

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]]

The brute-force matrix multiplication involves three nested loops iterating over rows of mat1, columns of mat2, and the shared dimension. However, many elements in mat1 and mat2 are zero, so multiplying zeros wastes computation. The algorithm optimizes by skipping multiplications involving zero elements. For example, in mat1, the element at row 0, column 1 is zero, so the inner loop skips all multiplications involving this zero. This reduces unnecessary operations, especially for sparse matrices.

Approach

Straightforward Solution

A naive approach uses three nested loops: iterate over each row of mat1, each column of mat2, and the shared dimension to compute each element of the result. This approach is O(n^3) and inefficient for large or sparse matrices.

Core Observation

Matrix multiplication requires summing products of corresponding elements from rows of the first matrix and columns of the second. The fundamental operation is the dot product of a row vector and a column vector.

Path to Optimal

Preview

The key insight is that many elements in the input matrices may be zero, especially in sparse matrices. Multiplying by zero yields zero, so these operations can be skipped…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Iterate over each row of mat1 and each element in that row. If the element is zero, skip to the next…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(rows1 * cols1 * cols2)

In the worst case, the algorithm visits every element in mat1 and mat2 relevant to the multiplication, resulting in cubic time relative to matrix dimensions. However, skipping zero elements reduces the actual operations for sparse matrices.

Space

O(rows1 * cols2)

The output matrix requires space proportional to the number of rows in mat1 and columns in mat2. The algorithm uses no additional significant auxiliary space beyond this.

Solution

Python

1class Solution:
  def multiply(self, mat1: list[list[int]], mat2: list[list[int]]) -> list[list[int]]:
      rows1 = len(mat1)
      cols1 = len(mat1[0])
      cols2 = len(mat2[0])
6
      result = [[0] * cols2 for _ in range(rows1)]
8
      for row in range(rows1):
          for middle in range(cols1):
              if mat1[row][middle] == 0:
                  continue
13
              for col in range(cols2):
                  if mat2[middle][col] == 0:
                      continue
17
                  result[row][col] += mat1[row][middle] * mat2[middle][col]
19
      return result

Step-by-Step Solution

1

Compute Matrix Dimensions and Initialize Result Matrix

3rows1 = len(mat1)
4cols1 = len(mat1[0])
5cols2 = len(mat2[0])
7result = [[0] * cols2 for _ in range(rows1)]

Objective

To determine the dimensions of the input matrices and create a zero-initialized result matrix with appropriate size.

Key Insight

Knowing the number of rows and columns in the input matrices is essential for controlling the iteration bounds. Initializing the result matrix with zeros ensures that accumulation of products can be done in-place without additional checks or resizing. This setup is foundational for the multiplication process.

Interview Quick-Check

Core Logic

Correctly computing dimensions ensures the loops iterate over valid indices, preventing index errors.

Common Pitfalls & Bugs

Forgetting to initialize the result matrix with zeros or with incorrect dimensions leads to incorrect results or runtime errors.

2

Traverse mat1 Rows and Columns, Skipping Zero Elements

To iterate over each element in mat1, skipping zero elements to avoid unnecessary multiplications.

3

Traverse mat2 Columns and Accumulate Products, Skipping Zero Elements

To iterate over each column in mat2 corresponding to the current element in mat1, skipping zero elements and accumulating the product into the result matrix.

4

Return the Computed Result Matrix

To return the fully computed product matrix after all accumulations are complete.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 3 Critical lines interviewers watch for.

Line 18 Critical

result[row][col] += mat1[row][middle] * mat2[middle][col]

Accumulate the product of mat1 and mat2 elements into the result matrix.

This line performs the core multiplication and addition step of matrix multiplication, building the final result incrementally and correctly.

Line 11 Critical

if mat1[row][middle] == 0:

Check if the current element in mat1 is zero.

Skipping zero elements in mat1 avoids unnecessary multiplications and additions, optimizing performance especially for sparse matrices.

Line 15 Critical

if mat2[middle][col] == 0:

Check if the current element in mat2 is zero.

Skipping zero elements in mat2 further reduces unnecessary multiplications, complementing the optimization from mat1.

Full line-by-line criticality + rationale for all 13 lines available on Pro.

Test Your Understanding

Why does checking for zero elements before multiplication improve performance without changing the result?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Sparse Matrix Multiplication from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Sparse Matrix Multiplication drill

or drill a free problem

1	`class Solution:`
2	`def multiply(self, mat1: list[list[int]], mat2: list[list[int]]) -> list[list[int]]:`
3	`rows1 = len(mat1)`
4	`cols1 = len(mat1[0])`
5	`cols2 = len(mat2[0])`
6
7	`result = [[0] * cols2 for _ in range(rows1)]`
8
9	`for row in range(rows1):`
10	`for middle in range(cols1):`
11	`if mat1[row][middle] == 0:`
12	`continue`
13
14	`for col in range(cols2):`
15	`if mat2[middle][col] == 0:`
16	`continue`
17
18	`result[row][col] += mat1[row][middle] * mat2[middle][col]`
19
20	`return result`

3	`rows1 = len(mat1)`
4	`cols1 = len(mat1[0])`
5	`cols2 = len(mat2[0])`
7	`result = [[0] * cols2 for _ in range(rows1)]`