Skip to main content
Talentd

Sparse Matrix Multiplication - Solution & Explanation

MediumPremiumFree on FleetCodeArrayHash TableMatrix12 min readAsked at: Amazon, Meta, Oracle +6
Practice this problem

Problem Statement

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 that multiplication is always possible.

 

Example 1:

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

Example 2:

Input: mat1 = [[0]], mat2 = [[0]]
Output: [[0]]

 

Constraints:

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

Approach Overview

Problem Overview: You are given two matrices mat1 and mat2. The task is to compute their matrix product. The twist is that the matrices are sparse, meaning most values are zero. A good solution avoids unnecessary multiplications with zero.

Approach 1: Direct Multiplication (O(m * n * p) time, O(1) extra space)

This approach follows the standard matrix multiplication rule. For each cell result[i][j], iterate through index k and compute mat1[i][k] * mat2[k][j]. The key optimization is skipping work when mat1[i][k] == 0, because multiplying by zero contributes nothing to the result. Implementation uses three nested loops over rows of mat1, columns of mat2, and the shared dimension. Even with the zero check, the worst‑case complexity remains O(m * n * p) where m, n, and p are the matrix dimensions. This approach is simple and readable but wastes time when matrices contain many zeros. It mainly relies on basic Array iteration and standard Matrix multiplication rules.

Approach 2: Preprocessing Non‑Zero Values (O(nnz(A) * p) average time, O(nnz(A) + nnz(B)) space)

Sparse matrices benefit from processing only non‑zero entries. First preprocess mat1 and record the column indices and values of non‑zero elements for every row. This structure can be stored using lists or a Hash Table. During multiplication, iterate through the stored non‑zero elements (i, k) from mat1. For each one, multiply it with the corresponding row k in mat2. Since the multiplication happens only when mat1[i][k] is non‑zero, the algorithm skips most useless operations. The runtime becomes proportional to the number of non‑zero values rather than the total matrix size. If nnz(A) is the number of non‑zero entries in mat1, the effective work is roughly O(nnz(A) * p) or better depending on sparsity in mat2. Extra space stores the non‑zero structure, but the speed improvement is significant for large sparse matrices.

Recommended for interviews: Interviewers expect the preprocessing approach. Starting with direct multiplication shows you understand matrix multiplication basics, but recognizing sparsity and skipping zero work demonstrates stronger algorithmic thinking. Mention the idea of storing only non‑zero elements and multiplying selectively. That insight turns a brute force triple loop into a solution that scales with the actual useful data rather than the full matrix size.

Approach 1: Direct Multiplication

We can directly calculate each element in the result matrix according to the definition of matrix multiplication.

The time complexity is O(m times n times k), and the space complexity is O(m times n). Where m and n are the number of rows of matrix mat1 and the number of columns of matrix mat2 respectively, and k is the number of columns of matrix mat1 or the number of rows of matrix mat2.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Approach 2: Preprocessing

We can preprocess the sparse representation of the two matrices, i.e., g1[i] represents the column index and value of all non-zero elements in the ith row of matrix mat1, and g2[i] represents the column index and value of all non-zero elements in the ith row of matrix mat2.

Next, we traverse each row i, traverse each element (k, x) in g1[i], traverse each element (j, y) in g2[k], then mat1[i][k] times mat2[k][j] will correspond to ans[i][j] in the result matrix, and we can accumulate all the results.

The time complexity is O(m times n times k), and the space complexity is O(m times n). Where m and n are the number of rows of matrix mat1 and the number of columns of matrix mat2 respectively, and k is the number of columns of matrix mat1 or the number of rows of matrix mat2.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Direct Multiplication—
Preprocessing—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Direct MultiplicationO(m * n * p)O(1)Small matrices or when sparsity is low and implementation simplicity matters
Direct Multiplication with Zero SkipO(m * n * p) worst caseO(1)Slight optimization when many values in the first matrix are zero
Preprocessing Non‑Zero Values~O(nnz(A) * p)O(nnz(A) + nnz(B))Large sparse matrices where skipping zero operations drastically reduces work

Video Solution

LeetCode 311. Sparse Matrix Multiplication • Happy Coding • 12,756 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Sparse Matrix Multiplication easy or hard?
The problem is considered medium difficulty. The basic matrix multiplication idea is straightforward, but recognizing that sparse matrices allow skipping zero operations is the key insight. Implementing the optimized approach requires careful iteration over non‑zero elements.
Sparse Matrix Multiplication Python/Java solution
Implementations usually preprocess rows of the first matrix and then multiply only non‑zero entries. Python often uses lists of pairs or dictionaries, while Java uses ArrayList or HashMap structures. The same logic works in C++, Go, and TypeScript with language‑specific containers.
How to solve Sparse Matrix Multiplication in O(n)?
Strict O(n) time is usually not possible for general matrix multiplication because each non‑zero element may affect multiple outputs. Practical sparse solutions run in time proportional to the number of non‑zero entries, often written as O(nnz). By preprocessing non‑zero values and skipping zeros, the algorithm avoids scanning the entire matrix.
What is the best approach for Sparse Matrix Multiplication?
The preprocessing approach that stores only non‑zero elements is the most efficient for sparse matrices. Instead of multiplying every cell, the algorithm iterates through non‑zero entries in the first matrix and multiplies them with relevant rows in the second matrix. This reduces unnecessary operations and makes the runtime depend on the number of non‑zero values rather than total matrix size.
Is Sparse Matrix Multiplication asked at Google/Amazon/Meta?
Sparse matrix problems appear in interviews at companies working with large‑scale data or graphics systems. Variants of this problem have been reported in interviews at companies like Google and Meta. The goal is to test understanding of matrix multiplication plus optimization using sparsity.
What data structure is used in Sparse Matrix Multiplication?
Efficient solutions typically store non‑zero entries using lists or hash maps. A common structure maps each row index to the column indices and values that are non‑zero. This allows the algorithm to iterate only over meaningful elements during multiplication.
What is the time complexity of Sparse Matrix Multiplication?
The naive matrix multiplication algorithm runs in O(m * n * p) time where m, n, and p are matrix dimensions. With sparse optimization, the runtime becomes closer to O(nnz(A) * p) or proportional to the number of non‑zero entries. This improvement is significant when the matrix contains mostly zeros.

Ready to solve this problem?

Practice Sparse Matrix Multiplication with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays