Formatted question description: https://leetcode.ca/all/1868.html
1868. Product of Two RunLength Encoded Arrays
Level
Medium
Description
Runlength 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 ith
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 runlength encoded arrayencoded = [[1,3],[2,5]]
. Another way to read this is “three1
s followed by five2
s”.
The product of two runlength encoded arrays encoded1
and encoded2
can be calculated using the following steps:
 Expand both
encoded1
andencoded2
into the full arraysnums1
andnums2
respectively.  Create a new array
prodNums
of lengthnums1.length
and setprodNums[i] = nums1[i] * nums2[i]
.  Compress
prodNums
into a runlength encoded array and return it.
You are given two runlength 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 ith
segment of nums1
, and each encoded2[j] = [val_j, freq_j]
describes the jth
segment of nums2
.
Return the product of encoded1
and encoded2
.
Note: Compression should be done such that the runlength 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 runlength 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 runlength 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
andencoded2
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; } }

Todo

print("Todo!")