> For the complete documentation index, see [llms.txt](https://liuyang89116.gitbook.io/my-leetcode-book/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://liuyang89116.gitbook.io/my-leetcode-book/post_chapter_3_array/problem_311_sparse_matrix_multiplication/problem-sparse-vectors-of-dot-product.md).

# Problem: Sparse vectors of dot product

## 思路

* 如果都是 sparse vector,那思路就是把每个 vector 都表示成 (index, non-zero value) pairs:

  ```
  A =[0,2,0,2,0,0,3,0,0,4] ==> A={(1,2), (3,2), (6,3), (9,4)}
  ```

  ```
  B=[0,0,0,0,5,0,2,0,0,8]  ==> B={(4,5), (6,2), (9,8)}
  ```
* for each index i, a = val of pair (i, v\_in\_A), b= val of pair (i, v\_in\_B).\
  dot\_product(A,B) = sum\_of ( a \* b )
* 复杂度： `O(m + n)`

## Follow Up

> what if the number of nonzero elements of one vector is 10^10 and the other is 10^2, how can you make it faster?

* 这里的区别就是，一个特别长一个特别短。那么我们就先扫短的，然后用二分法再长的里面找对应的 index。复杂度应该是 `O(m * log n)`