## Question

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`

## Algorithm

First you need to know what's matrix, then you need to know how to do the matrix multiplication.

This graph is the key:

The logic behind the scene is worth to discuss. What do this and what's the meaning.

The steps of implementation can be found in the wiki page or the graph.

## Code

class Solution { public int[][] multiply(int[][] mat1, int[][] mat2) { int m = mat1.length; int k = mat1[0].length; int n = mat2[0].length; int[][] res = new int[m][n]; for (int i = 0; i < m; i++) { for (int j = 0; j < k; j++) { int num = mat1[i][j]; for (int x = 0; x < n; x++) { res[i][x] += num * mat2[j][x]; } } } return res; } }

However, the matrix we use to calculate is a **sparse** matrix which we could utilize this attribute and reduce the calculation a little bit.

class Solution { public int[][] multiply(int[][] mat1, int[][] mat2) { int m = mat1.length; int k = mat1[0].length; int n = mat2[0].length; int[][] res = new int[m][n]; for (int i = 0; i < m; i++) { for (int j = 0; j < k; j++) { if (mat1[i][j] != 0) { int num = mat1[i][j]; for (int x = 0; x < n; x++) { if (mat2[j][x] != 0) { res[i][x] += num * mat2[j][x]; } } } } } return res; } }