Show problems as
Classic problem #311MediumArrayHash TableMatrixLinear Algebra

Sparse Matrix Multiplication

Real-world version: Multiplying Two Mostly Empty Tables
Tracked in this browser only
Read Sparse Matrix Multiplication on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Two tables of numbers are given, left and right, where the number of columns in left equals the number of rows in right. Most entries of both are 0.

Their product is the table whose entry in row i and column j comes from running along row i of left and down column j of right at the same time, multiplying each pair of entries that meet and adding those products up.

Return the product.

Examples

Example 1

Input
left = [[2, 0], [0, 3]], right = [[0, 5], [7, 0]]
Output
[[0, 10], [21, 0]]

The first row of the answer comes from 2 meeting the first column's 0 and 7, giving nothing, and 2 meeting the second column's 5 and 0, giving ten. The second row comes the same way from the 3.

Example 2

Input
left = [[1, 2, 3]], right = [[4], [5], [6]]
Output
[[32]]

A single row against a single column leaves a one-entry answer: the three pairs that meet give four, ten and eighteen, adding to thirty-two.

Example 3

Input
left = [[0, 0], [0, 0]], right = [[0, 0], [0, 0]]
Output
[[0, 0], [0, 0]]

Every entry of both tables is nothing, so every pair that meets contributes nothing.

Constraints

  • 1 <= left.length <= 100
  • 1 <= left[i].length <= 100
  • 1 <= right[i].length <= 100
  • The number of columns in left equals the number of rows in right.
  • -100 <= left[i][j] <= 100
  • -100 <= right[i][j] <= 100

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def multiply(left: list[list[int]], right: list[list[int]]) -> list[list[int]]:
Java
public int[][] multiply(int[][] left, int[][] right)

More on the same topics