> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Product of Two Run-Length Encoded Arrays

> Tested Python solution for LeetCode 1868 with 24 pytest cases. Generate a practice environment with lcpy.

LeetCode 1868, [Medium](/catalog/medium). Topics: [Array](/catalog/topics/array), [Two Pointers](/catalog/topics/two-pointers). [View on LeetCode](https://leetcode.com/problems/product-of-two-run-length-encoded-arrays/description/).

Generate this problem as a practice environment: tested reference solution, 24 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 1868   # by problem number
lcpy gen -s product_of_two_run_length_encoded_arrays   # by problem name
```

## Problem

**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:

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

### Examples

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

```
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

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/product_of_two_run_length_encoded_arrays/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/product_of_two_run_length_encoded_arrays/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(m + n)
    # Space: O(1) extra (excluding the output)
    def find_rle_array(
        self, encoded1: list[list[int]], encoded2: list[list[int]]
    ) -> list[list[int]]:
        result: list[list[int]] = []
        i = j = 0
        left1 = encoded1[0][1]
        left2 = encoded2[0][1]
        while i < len(encoded1) and j < len(encoded2):
            take = min(left1, left2)
            product = encoded1[i][0] * encoded2[j][0]
            if result and result[-1][0] == product:
                result[-1][1] += take
            else:
                result.append([product, take])
            left1 -= take
            left2 -= take
            if left1 == 0:
                i += 1
                if i < len(encoded1):
                    left1 = encoded1[i][1]
            if left2 == 0:
                j += 1
                if j < len(encoded2):
                    left2 = encoded2[j][1]
        return result
```

## Complexity

| Time | Space |
| - | - |
| O(m + n) | O(1) extra (excluding the output) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.