Sparse Matrix Multiplication

medium array matrix hash map

Problem

Given two sparse matrices A and B (most entries are 0), return A · B.

InputA = [[1,0,0],[-1,0,3]], B = [[7,0,0],[0,0,0],[0,0,1]]

Output[[7,0,0],[-7,0,3]]

Only A[0][0]=1 and A[1][0]=-1, A[1][2]=3 contribute.

A (rows ';' cells ',')

B (rows ';' cells ',')

def multiply(A, B):
    m, n, p = len(A), len(A[0]), len(B[0])
    C = [[0]*p for _ in range(m)]
    for i in range(m):
        for k in range(n):
            if A[i][k] == 0: continue
            for j in range(p):
                if B[k][j] != 0:
                    C[i][j] += A[i][k] * B[k][j]
    return C

function multiply(A, B) {
  const m = A.length, n = A[0].length, p = B[0].length;
  const C = Array.from({length: m}, () => new Array(p).fill(0));
  for (let i = 0; i < m; i++)
    for (let k = 0; k < n; k++) {
      if (A[i][k] === 0) continue;
      for (let j = 0; j < p; j++)
        if (B[k][j] !== 0) C[i][j] += A[i][k] * B[k][j];
    }
  return C;
}

class Solution {
    public int[][] multiply(int[][] A, int[][] B) {
        int m = A.length, n = A[0].length, p = B[0].length;
        int[][] C = new int[m][p];
        for (int i = 0; i < m; i++)
            for (int k = 0; k < n; k++) {
                if (A[i][k] == 0) continue;
                for (int j = 0; j < p; j++)
                    if (B[k][j] != 0) C[i][j] += A[i][k] * B[k][j];
            }
        return C;
    }
}

vector> multiply(vector>& A, vector>& B) {
    int m = A.size(), n = A[0].size(), p = B[0].size();
    vector> C(m, vector(p, 0));
    for (int i = 0; i < m; i++)
        for (int k = 0; k < n; k++) {
            if (A[i][k] == 0) continue;
            for (int j = 0; j < p; j++)
                if (B[k][j] != 0) C[i][j] += A[i][k] * B[k][j];
        }
    return C;
}

Explanation

Normal matrix multiplication does a lot of pointless work when the matrices are sparse (mostly zeros), because multiplying by zero adds nothing. The trick here is to skip the zeros so we only do real work where it matters.

We loop over each row i of A and each column index k. The key line is if A[i][k] == 0: continue — if that cell of A is zero, the whole inner loop would just add zeros, so we skip it entirely.

When A[i][k] is non-zero, it pairs with row k of B. For each column j we add A[i][k] * B[k][j] into C[i][j]. We even skip the multiply when B[k][j] is zero.

This still produces the exact standard product A · B; we just avoid the additions that contribute nothing.

Example: A = [[1,0,0],[-1,0,3]]. In row 1, only A[1][0]=-1 and A[1][2]=3 survive the skip. They combine with rows 0 and 2 of B to give the output row [-7,0,3].

Time: O(m · n · p) Space: O(m · p)