1868. Product of Two Run-Length Encoded Arrays

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.

class Solution {
public:
    vector<vector<int>> findRLEArray(vector<vector<int>>& encoded1, vector<vector<int>>& encoded2) {
        vector<vector<int>> res;
        for(int i = 0, j = 0; i < encoded1.size() and j < encoded2.size();) {
            int freq = min(encoded1[i][1], encoded2[j][1]);
            int val = encoded1[i][0] * encoded2[j][0];
            
            if(res.empty() or res.back()[0] != val)
                res.push_back({val, freq});
            else res.back()[1] += freq;
            
            encoded1[i][1] -= freq;
            encoded2[j][1] -= freq;
            if(encoded1[i][1] == 0) i++;
            if(encoded2[j][1] == 0) j++;
        }
        return res;
    }
};