Sparse matrix multiplication

Array Hash Table Matrix

69.3% acceptance

Mar 31, 2026

1129

374

Given two sparse matrices mat1 of size m x k and mat2 of size k x n, return the result of mat1 x mat2. You may assume that multiplication is always possible.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn multiply(mat1: Vec<Vec<i32>>, mat2: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    let m = mat1.len();
    let k = mat1[0].len();
    let n = mat2[0].len();
    let mut result = vec![vec![0; n]; m];
    for i in 0..m {
      for p in 0..k {
        if mat1[i][p] != 0 {
          for j in 0..n {
            if mat2[p][j] != 0 {
              result[i][j] += mat1[i][p] * mat2[p][j];
            }
          }
        }
      }
    }
    result
  }
}