311. Sparse Matrix Multiplication

leetcode medium

#array#csharp#leetcode#matrix#medium#string

Task

Даны две разреженные матрицы mat1 размером m x k и mat2 размером k x n. Верните результат перемножения матриц mat1 x mat2. Вы можете предположить, что умножение всегда возможно.

Пример:

Input: mat1 = [[1,0,0],[-1,0,3]], mat2 = [[7,0,0],[0,0,0],[0,0,1]]

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

C# solution

matched/original

public class Solution {
    public int[][] Multiply(int[][] mat1, int[][] mat2) {
        int n = mat1.Length;
        int k = mat1[0].Length;
        int m = mat2[0].Length;
        int[][] ans = new int[n][];
        for (int i = 0; i < n; i++) {
            ans[i] = new int[m];
        }
        for (int rowIndex = 0; rowIndex < n; rowIndex++) {
            for (int elementIndex = 0; elementIndex < k; elementIndex++) {
                if (mat1[rowIndex][elementIndex] != 0) {
                    for (int colIndex = 0; colIndex < m; colIndex++) {
                        ans[rowIndex][colIndex] += mat1[rowIndex][elementIndex] * mat2[elementIndex][colIndex];
                    }
                }
            }
        }
        return ans;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int[][] Multiply(int[][] mat1, int[][] mat2) {
        int n = mat1.size();
        int k = mat1[0].size();
        int m = mat2[0].size();
        int[][] ans = new int[n][];
        for (int i = 0; i < n; i++) {
            ans[i] = new int[m];
        }
        for (int rowIndex = 0; rowIndex < n; rowIndex++) {
            for (int elementIndex = 0; elementIndex < k; elementIndex++) {
                if (mat1[rowIndex][elementIndex] != 0) {
                    for (int colIndex = 0; colIndex < m; colIndex++) {
                        ans[rowIndex][colIndex] += mat1[rowIndex][elementIndex] * mat2[elementIndex][colIndex];
                    }
                }
            }
        }
        return ans;
    }
}

Java solution

matched/original

public class Solution {
    public int[][] multiply(int[][] mat1, int[][] mat2) {
        int n = mat1.length;
        int k = mat1[0].length;
        int m = mat2[0].length;
        
        int[][] ans = new int[n][m];
        
        for (int rowIndex = 0; rowIndex < n; rowIndex++) {
            for (int elementIndex = 0; elementIndex < k; elementIndex++) {
                if (mat1[rowIndex][elementIndex] != 0) {
                    for (int colIndex = 0; colIndex < m; colIndex++) {
                        ans[rowIndex][colIndex] += mat1[rowIndex][elementIndex] * mat2[elementIndex][colIndex];
                    }
                }
            }
        }
        
        return ans;
    }
}

JavaScript solution

matched/original

var multiply = function(mat1, mat2) {
    let n = mat1.length;
    let k = mat1[0].length;
    let m = mat2[0].length;
    
    let ans = Array.from({ length: n }, () => Array(m).fill(0));
    
    for (let rowIndex = 0; rowIndex < n; rowIndex++) {
        for (let elementIndex = 0; elementIndex < k; elementIndex++) {
            if (mat1[rowIndex][elementIndex] !== 0) {
                for (let colIndex = 0; colIndex < m; colIndex++) {
                    ans[rowIndex][colIndex] += mat1[rowIndex][elementIndex] * mat2[elementIndex][colIndex];
                }
            }
        }
    }
    
    return ans;
};

Python solution

matched/original

class Solution:
    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:
        n = len(mat1)
        k = len(mat1[0])
        m = len(mat2[0])
        
        ans = [[0] * m for _ in range(n)]
        
        for rowIndex in range(n):
            for elementIndex in range(k):
                if mat1[rowIndex][elementIndex] != 0:
                    for colIndex in range(m):
                        ans[rowIndex][colIndex] += mat1[rowIndex][elementIndex] * mat2[elementIndex][colIndex]
        
        return ans

Go solution

matched/original

func multiply(mat1 [][]int, mat2 [][]int) [][]int {
    n := len(mat1)
    k := len(mat1[0])
    m := len(mat2[0])
    
    ans := make([][]int, n)
    for i := range ans {
        ans[i] = make([]int, m)
    }
    
    for rowIndex := 0; rowIndex < n; rowIndex++ {
        for elementIndex := 0; elementIndex < k; elementIndex++ {
            if mat1[rowIndex][elementIndex] != 0 {
                for colIndex := 0; colIndex < m; colIndex++ {
                    ans[rowIndex][colIndex] += mat1[rowIndex][elementIndex] * mat2[elementIndex][colIndex]
                }
            }
        }
    }
    
    return ans
}

Explanation

Algorithm

Инициализация результирующей матрицы

Создайте результирующую матрицу result размером m x n, заполненную нулями.

Хранение ненулевых элементов

Пройдите по каждой строке матрицы mat1 и сохраните индексы и значения ненулевых элементов в хеш-карте mat1_map. Пройдите по каждой колонке матрицы mat2 и сохраните индексы и значения ненулевых элементов в хеш-карте mat2_map.

Вычисление произведения

Для каждой строки i в mat1 и для каждой колонки j в mat2: Если в mat1_map есть ненулевой элемент в строке i и в mat2_map есть ненулевой элемент в колонке j с одинаковым индексом k, добавьте произведение этих элементов к result[i][j].

😎