Matrix coding pattern

Sparse matrix

Sparse vectors are vectors where most of the elements are zero.

1D Vector

Original vector: [0,3,0,4,0]

Compressed vector: [[1,3],[3,4]]

Here each non zero value are stored as per their index position as [i,value] , other zero values are dropped. Assumption is, rest are zero value.

2D Vector

Original vector

[
  [7,0,1],
  [0,0,0],
  [0,0,1]
]

In similar way, we can compress it as below.

[
  [[0,7],[2,1]],
  [],
  [2,1]
]

1570. Dot Product of Two Sparse Vectors

https://leetcode.com/problems/dot-product-of-two-sparse-vectors/

Given two sparse vectors, compute their dot product.

Implement class SparseVector:

• SparseVector(nums) Initializes the object with the vector nums
• dotProduct(vec) Compute the dot product between the instance of SparseVector and vec

A sparse vector is a vector that has mostly zero values, you should store the sparse vector efficiently and compute the dot product between two SparseVector.

Approach

1. Since Sparse vector has lot of zeros therefore 1d storage will waste lot of spaces.
2. We can only store the <index, value> for non zeros as 2d storage.

Following is example to represent two Sparse vector.

[1,0,0,2,3]          [0,3,0,4,0]
Row   Value          Row    Value
0     1              1      3
3     2              3      4
4     3

3. Multiply common index, other index multiplication will lead to 0 therefore we can ignore it.

Following is the code to implement it.

/**
 * @param {number[]} nums
 * @return {SparseVector}
 */
var SparseVector = function(nums) {
    this.data = [];
    for(let i=0; i < nums.length; i++) {
        if(nums[i] !== 0) {
            this.data.push([i, nums[i]])
        }
    }
};

// Return the dotProduct of two sparse vectors
/**
 * @param {SparseVector} vec
 * @return {number}
 */
SparseVector.prototype.dotProduct = function(vec) {
    const v1 = vec.data; 
    const v2 = this.data;

    let i = 0;
    let j = 0;
    let total = 0;
    while(i < v1.length && j < v2.length) {
        if(v1[i][0] === v2[j][0]) { // Same index, use for multiplication
            total += v1[i][1] * v2[j][1];
            i++;
            j++;
        } else if (v1[i][0] < v2[j][0]) { // To ignore, skip the lowest
            i++;
        } else {
            j++;
        }
    }
    return total;
};

311. Sparse Matrix Multiplication

https://leetcode.com/problems/sparse-matrix-multiplication/description/

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.

Approach

To reduce the waste to store the many zeros, we can create bucket for each row which will contain a pair <value, column> for non zeros value only.

Multiply only the non-zero elements of mat1 with the non-zero elements of a particular row of mat2 to multiply matrices.

Following will be the steps for algorithm.

1. Compress matrix to store only non zeros values.
2. A is compressed matrix for mat1 and B is compressed matrix for mat2
3. For each row in A , iterate over all elements.
4. For each element, we get (value, col) pair and iterate over all the elements of col th row in B.
5. For each pair of elements, we add their product to the ans matrix.

Note: In original matrix multuplication, cell (i,j) is calcualted in one loop. In compressed format, cell (i,j) is calculated one by one.

Following is the code to implement this approach.

const compressMatrix = matrix => {
    const m = matrix.length;
    const n = matrix[0].length;
    const compressed = [];
    for (let i = 0; i < m; i++) {
        const row = [];
        for (let j = 0; j < n; j++) {
            const cell = matrix[i][j];
            if (cell !== 0) {
                row.push([cell, j]);
            }
        }
        compressed.push(row);
    }
    return compressed;
}
/**
 * @param {number[][]} mat1
 * @param {number[][]} mat2
 * @return {number[][]}
 */
var multiply = function (mat1, mat2) {
    const m = mat1.length;
    const k = mat1[0].length;
    const n = mat2[0].length;

    const A = compressMatrix(mat1);
    const B = compressMatrix(mat2);

    const ans = new Array(m).fill(0).map(a => new Array(n).fill(0));
    for (let i = 0; i < m; i++) {
        // Iterate on all current 'row' non-zero elements of mat1.
        for (const [v1, c1] of A[i]) {
            // Multiply and add all non-zero elements of mat2
            // where the row is equal to col of current element of mat1.
            for (const [v2, c2] of B[c1]) {
                ans[i][c2] += v1 * v2;
            }
        }
    }
    return ans;

};

1868. Product of Two Run-Length Encoded Arrays

https://leetcode.com/problems/product-of-two-run-length-encoded-arrays/description

Run-length encoding is a compression algorithm that allows for an integer array nums with many segments of consecutive repeated numbers to be represented by a (generally smaller) 2D array encoded. Each encoded[i] = [vali, freqi] describes the ith segment of repeated numbers in nums where vali is the value that is repeated freqi times.

• For example, nums = [1,1,1,2,2,2,2,2] is represented by the run-length encoded array encoded = [[1,3],[2,5]]. Another way to read this is "three 1's followed by five 2's".

The product of two run-length encoded arrays encoded1 and encoded2 can be calculated using the following steps:

1. Expand both encoded1 and encoded2 into the full arrays nums1 and nums2 respectively.
2. Create a new array prodNums of length nums1.length and set prodNums[i] = nums1[i] * nums2[i].
3. Compress prodNums into a run-length encoded array and return it.

You are given two run-length encoded arrays encoded1 and encoded2 representing full arrays nums1 and nums2 respectively. Both nums1 and nums2 have the same length. Each encoded1[i] = [vali, freqi] describes the ith segment of nums1, and each encoded2[j] = [valj, freqj] describes the jth segment of nums2.

Return the product of encoded1 and encoded2.

Note: Compression should be done such that the run-length encoded array has the minimum possible length.

Example 1:

Input: encoded1 = [[1,3],[2,3]], encoded2 = [[6,3],[3,3]]
Output: [[6,6]]
Explanation: encoded1 expands to [1,1,1,2,2,2] and encoded2 expands to [6,6,6,3,3,3].
prodNums = [6,6,6,6,6,6], which is compressed into the run-length encoded array [[6,6]].

Approach #1 (TLE): Expand, multiply followed by encode again

We can expand the given two arrays, then multiply followed by encode it again. But it will lead to TLE. Following is code for reference.

const expand = encoded => {
    const ans = [];
    for (const [val, freq] of encoded) {
        for (let i = 0; i < freq; i++) {
            ans.push(val);
        }
    }
    return ans;
}
const product = (nums1, nums2) => {
    const ans = [];
    for (let i = 0; i < nums1.length; i++) {
        ans.push(nums1[i] * nums2[i]);
    }
    return ans;
}
const encode = nums => {
    const ans = [];
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        const num = nums[i];
        let freq = 1;
        while (i < n && nums[i] === nums[i + 1]) {
            freq++;
            i++;
        }
        ans.push([num, freq])
    }
    return ans;
}
/**
 * @param {number[][]} encoded1
 * @param {number[][]} encoded2
 * @return {number[][]}
 */
var findRLEArray = function (encoded1, encoded2) {
    const nums1 = expand(encoded1);
    const nums2 = expand(encoded2);
    const nums = product(nums1, nums2);
    return encode(nums);
};

Approach#2: Use two pointers and single pass

Instead of expanding the encoded arrays, we can take following approach

• Take 2 pointers on each array
• In first pass, build the intermediate result as below
• If frequency is same for both then add product into result and increment both counter.
• If f1<f2 , it means we can add <product,f1> into result and reduce f2-f1 value to encoded2
• Otherwise do similar for f1>f2
• This builds the results and it might have few unmerged.
• Need to run separate pass to apply run length encoding on the shorter results.

Following is code for reference.

/**
 * @param {number[][]} encoded1
 * @param {number[][]} encoded2
 * @return {number[][]}
 */
var findRLEArray = function (encoded1, encoded2) {
    const m = encoded1.length;
    const n = encoded2.length;
    let i = 0, j = 0, v1 = 0, v2 = 0, f1 = 0, f2 = 0;
    let result = [];
    while (i < m && j < n) {
        // Read value
        [v1, f1] = encoded1[i];
        [v2, f2] = encoded2[j];
        const product = v1 * v2;
        if (f1 === f2) {
            result.push([product, f1]);
            i++;
            j++;
        } else if (f1 < f2) {
            result.push([product, f1]);
            encoded2[j][1] = f2 - f1;
            i++;
        } else {
            result.push([product, f2]);
            encoded1[i][1] = f1 - f2;
            j++;
        }
    }
    // Apply merging
    const ans = [];
    let prev = result[0];
    for (let i = 1; i < result.length; i++) {
        const curr = result[i];
        if (curr[0] !== prev[0]) {
            // If different from prev, add to result
            ans.push(prev);
            prev = curr;
        } else {
            // if same as prev, then add freq
            prev[1] += curr[1];
        }
    }
    // Add the last one
    ans.push(prev);
    return ans;
};

Happy coding :-)