1015MediumArrayHash TableMatrixLinear Algebra

Multiplying Two Mostly Empty Tables

Tracked in this browser only

Trains the technique from

LeetCode 311Sparse Matrix Multiplication

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

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

Java

public int[][] multiply(int[][] left, int[][] right)

The intended approach

Time O(m*k + k*n + P) for tables of m by k and k by n, with P pairs of non-empty entries meeting.Space O(m*n + k*n) for the answer and the gathered entries.

Read straight off, the product multiplies every entry of a row by every entry of a column, and nearly all of those products come to nothing because nearly all the entries do. Never forming them is the whole gain. Turn the sum inside out. Walk `left` row by row, and within a row visit only the entries that are not nothing. Such an entry sits in some column of `left`, and that column names a row of `right`. Walk that row of `right`, again only over its entries that are not nothing, and add the product straight into the answer's current row at the column where the entry sat. Every pair of non-empty entries that actually meets is handled exactly once, and no pair whose product would be nothing is ever touched. Gathering each row of `right` into its non-empty entries once, before the walk starts, stops that row being rescanned for every row of `left`.

Pythonentry point: multiply

def multiply(left, right):
    rows = len(left)
    mid = len(right)
    cols = len(right[0])
    packed = []
    for r in range(mid):
        here = []
        for c in range(cols):
            if right[r][c]:
                here.append((c, right[r][c]))
        packed.append(here)
    out = [[0] * cols for _ in range(rows)]
    for r in range(rows):
        line = out[r]
        for m in range(mid):
            value = left[r][m]
            if value == 0:
                continue
            for c, other in packed[m]:
                line[c] += value * other
    return out

The obvious version

Take each row of the answer and each column in turn, run down the whole meeting range multiplying and adding every pair whether or not either is nothing, and write the total in. Costs the full three nested walks rather than only the pairs that matter.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_multiply(left, right):
    rows = len(left)
    mid = len(right)
    cols = len(right[0])
    out = []
    for r in range(rows):
        line = []
        for c in range(cols):
            total = 0
            for m in range(mid):
                total += left[r][m] * right[m][c]
            line.append(total)
        out.append(line)
    return out

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in