Sparse Matrix Multiplication

Medium Arrays & Hashing Matrix Traversal Original on LeetCode

Reported atApplePinterest

Sparse Matrix Multiplication is a medium arrays & hashing problem solved with the matrix traversal pattern. The best approach, optimal (skip zeros with compressed rows), runs in O(m · k + k · n + Z) time and O(k · n) for the compressed rows space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (textbook triple loop) up.

Problem

You are given two integer matrices: mat1 of size m x k and mat2 of size k x n. Return their matrix product, an m x n matrix whose cell (i, c) equals the sum of mat1[i][j] * mat2[j][c] over every j.

Both inputs are sparse: most of their entries are 0. Aim for a solution that does not waste work multiplying zeros.

Examples

Example 1

Input
mat1 = [[2, 0, 0], [0, 0, -1]], mat2 = [[0, 4], [5, 0], [0, 3]]
Output
[[0, 8], [0, -3]]
Why
Row 0 only uses 2 * mat2[0] = [0, 8]; row 1 only uses -1 * mat2[2] = [0, -3].

Example 2

Input
mat1 = [[0, 0]], mat2 = [[7], [9]]
Output
[[0]]
Why
A row of zeros produces a row of zeros, whatever mat2 holds.

Constraints

  • mat1 is m x k and mat2 is k x n
  • 1 <= m, n, k <= 100
  • -100 <= mat1[i][j], mat2[i][j] <= 100

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (textbook triple loop)O(m · k · n)O(1) extra
Optimal (skip zeros with compressed rows)O(m · k + k · n + Z)O(k · n) for the compressed rows

1Brute force (textbook triple loop)

TimeO(m · k · n)Every one of the m · n cells does k multiplications, zero or not.
SpaceO(1) extraOnly the output matrix is allocated.

Compute every cell of the result as the dot product of a row of mat1 with a column of mat2, multiplying zeros along with everything else.

  1. Create an m x n result filled with 0.
  2. For each i in [0, m) and c in [0, n), sum mat1[i][j] * mat2[j][c] over j in [0, k).
class Solution {
    public int[][] multiply(int[][] mat1, int[][] mat2) {
        int m = mat1.length, k = mat2.length, n = mat2[0].length;
        int[][] res = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int c = 0; c < n; c++) {
                int sum = 0;
                for (int j = 0; j < k; j++) sum += mat1[i][j] * mat2[j][c];
                res[i][c] = sum;
            }
        }
        return res;
    }
}

2Optimal (skip zeros with compressed rows)

TimeO(m · k + k · n + Z)Scanning both matrices costs m · k + k · n; Z is the number of non-zero pairs actually multiplied, which is tiny for sparse inputs.
SpaceO(k · n) for the compressed rowsAt most every entry of `mat2` is stored once in the compressed lists.

Row i of the result is the sum of mat1[i][j] times row j of mat2. First store, for every row of mat2, only its non-zero (column, value) pairs. Then for each non-zero mat1[i][j], add its products with those pairs into row i. Zero entries of either matrix are never multiplied.

  1. For each row j of mat2, build a list of (column, value) for its non-zero entries.
  2. For each i and j with mat1[i][j] != 0, for each (c, v) in row j's list, do res[i][c] += mat1[i][j] * v.
  3. Return res.
class Solution {
    public int[][] multiply(int[][] mat1, int[][] mat2) {
        int m = mat1.length, k = mat2.length, n = mat2[0].length;
        List<List<int[]>> rows = new ArrayList<>();
        for (int j = 0; j < k; j++) {
            List<int[]> nz = new ArrayList<>();
            for (int c = 0; c < n; c++) {
                if (mat2[j][c] != 0) nz.add(new int[] { c, mat2[j][c] });
            }
            rows.add(nz);
        }
        int[][] res = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < k; j++) {
                int a = mat1[i][j];
                if (a == 0) continue;
                for (int[] e : rows.get(j)) res[i][e[0]] += a * e[1];
            }
        }
        return res;
    }
}

Edge cases to test

  • 1 x 1 matrices
  • A matrix that is entirely zero
  • Fully dense matrices (no zeros at all)
  • Negative entries that cancel to 0 in the product
  • A column vector times a row vector (k = 1), giving a full m x n result

Hints

Hint 1

Write out res[i][c] = sum over j of mat1[i][j] * mat2[j][c]. Which terms of this sum are guaranteed to be 0?

Hint 2

Loop over i, then j, and skip immediately when mat1[i][j] == 0; a non-zero mat1[i][j] adds a scaled copy of row j of mat2 into row i of the result.

Hint 3

Pre-collect the non-zero entries of each row of mat2 so the inner loop touches only those.

FAQ

What is the best time complexity for Sparse Matrix Multiplication?

Optimal (skip zeros with compressed rows) runs in O(m · k + k · n + Z) time and O(k · n) for the compressed rows extra space. Scanning both matrices costs m · k + k · n; Z is the number of non-zero pairs actually multiplied, which is tiny for sparse inputs.

Which pattern does Sparse Matrix Multiplication use?

It is a arrays & hashing problem that uses the matrix traversal pattern. Other problems with the same pattern: Spiral Matrix, Best Meeting Point, Diagonal Traverse.

Is there a brute force solution for Sparse Matrix Multiplication?

Yes. Brute force (textbook triple loop) takes O(m · k · n) time and O(1) extra space. Compute every cell of the result as the dot product of a row of mat1 with a column of mat2, multiplying zeros along with everything else.

Which edge cases should I test for Sparse Matrix Multiplication?

1 x 1 matrices; A matrix that is entirely zero; Fully dense matrices (no zeros at all); Negative entries that cancel to 0 in the product; A column vector times a row vector (k = 1), giving a full m x n result.