> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Sparse Matrix Multiplication Python Solution

> Tested Python solution for LeetCode 311 with 15 pytest cases. Generate a practice environment with lcpy.

LeetCode 311, [Medium](/catalog/medium). Topics: [Array](/catalog/topics/array), [Hash Table](/catalog/topics/hash-table), [Matrix](/catalog/topics/matrix). [View on LeetCode](https://leetcode.com/problems/sparse-matrix-multiplication/description/).

Generate this problem as a practice environment: tested reference solution, 15 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 311   # by problem number
lcpy gen -s sparse_matrix_multiplication   # by problem name
```

## Problem

Given two [sparse matrices](https://en.wikipedia.org/wiki/Sparse_matrix) `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.

### Examples

![Example 1](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/0300-0399/0311.Sparse%20Matrix%20Multiplication/images/mult-grid.jpg)

```
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 = [[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`

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/sparse_matrix_multiplication/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/sparse_matrix_multiplication/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(m * k * n) worst case, but skips zero entries of mat1 and mat2
    # Space: O(m * n)
    def multiply(self, mat1: list[list[int]], mat2: list[list[int]]) -> list[list[int]]:
        m, n = len(mat1), len(mat2[0])
        result = [[0] * n for _ in range(m)]
        # Pre-compute non-zero (column, value) pairs per row of mat2.
        mat2_nonzero = [[(j, val) for j, val in enumerate(row) if val != 0] for row in mat2]
        for i, row in enumerate(mat1):
            for t, mat1_val in enumerate(row):
                if mat1_val == 0:
                    continue
                for j, mat2_val in mat2_nonzero[t]:
                    result[i][j] += mat1_val * mat2_val
        return result
```

## Complexity

| Time | Space |
| - | - |
| O(m \* k \* n) worst case, but skips zero entries of mat1 and mat2 | O(m \* n) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.