Formatted question description: https://leetcode.ca/all/1868.html

# 1868. Product of Two Run-Length Encoded Arrays

## Level

Medium

## 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] = [val_i, freq_i]`

describes the `i-th`

segment of repeated numbers in nums where `val_i`

is the value that is repeated `freq_i`

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:

**Expand**both`encoded1`

and`encoded2`

into the full arrays`nums1`

and`nums2`

respectively.- Create a new array
`prodNums`

of length`nums1.length`

and set`prodNums[i] = nums1[i] * nums2[i]`

. **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] = [val_i, freq_i]`

describes the `i-th`

segment of `nums1`

, and each `encoded2[j] = [val_j, freq_j]`

describes the `j-th`

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]].

**Example 2:**

**Input:** encoded1 = [[1,3],[2,1],[3,2]], encoded2 = [[2,3],[3,3]]

**Output:** [[2,3],[6,1],[9,2]]

**Explanation:** encoded1 expands to [1,1,1,2,3,3] and encoded2 expands to [2,2,2,3,3,3].

prodNums = [2,2,2,6,9,9], which is compressed into the run-length encoded array [[2,3],[6,1],[9,2]].

**Constraints:**

`1 <= encoded1.length, encoded2.length <= 10^5`

`encoded1[i].length == 2`

`encoded2[j].length == 2`

`1 <= val_i, freq_i <= 10^4 for each encoded1[i]`

.`1 <= val_j, freq_j <= 10^4 for each encoded2[j]`

.- The full arrays that
`encoded1`

and`encoded2`

represent are the same length.

## Solution

Considering the constraints, it is impossible to expand both arrays and it is also impossible to store the uncompressed `prodNums`

. Therefore, all the operations must be done on compessed arrays.

Use two pointers to point to indices of both `encoded1`

and `encoded2`

. For the current values at `index1`

of `encoded1`

and `index2`

of `encoded2`

, the current product is `encoded1[index1][0] * encoded2[index2][0]`

and the current frequency is the minimum of `encoded1[index1][1]`

and `encoded2[index2][1]`

. If the current product is equal to the previous product, then update the product’s frequency. Otherwise, add the previous product and its frequency into the result list and update the product and the frequency. Finally, return the result list.

```
class Solution {
public List<List<Integer>> findRLEArray(int[][] encoded1, int[][] encoded2) {
List<List<Integer>> products = new ArrayList<List<Integer>>();
int product = 0, count = 0;
int length1 = encoded1.length, length2 = encoded2.length;
int index1 = 0, index2 = 0;
while (index1 < length1 && index2 < length2) {
int val1 = encoded1[index1][0], val2 = encoded2[index2][0];
int freq = Math.min(encoded1[index1][1], encoded2[index2][1]);
encoded1[index1][1] -= freq;
encoded2[index2][1] -= freq;
int curProduct = val1 * val2;
if (curProduct == product)
count += freq;
else {
if (count > 0)
products.add(Arrays.asList(product, count));
product = curProduct;
count = freq;
}
if (encoded1[index1][1] == 0)
index1++;
if (encoded2[index2][1] == 0)
index2++;
}
products.add(Arrays.asList(product, count));
return products;
}
}
```