## Product of Two Run-Length Encoded Arrays

• Time:O(|\texttt{encoded1}| + |\texttt{encoded2}|)
• Space:O(|\texttt{encoded1}| + |\texttt{encoded2}|)

## C++

``````class Solution {
public:
vector<vector<int>> findRLEArray(vector<vector<int>>& encoded1,
vector<vector<int>>& encoded2) {
vector<vector<int>> ans;
int i = 0;  // encoded1's index
int j = 0;  // encodes2's index

while (i < encoded1.size() && j < encoded2.size()) {
const int mult = encoded1[i][0] * encoded2[j][0];
const int minFreq = min(encoded1[i][1], encoded2[j][1]);
if (!ans.empty() && mult == ans.back()[0])
ans.back()[1] += minFreq;
else
ans.push_back({mult, minFreq});
encoded1[i][1] -= minFreq;
encoded2[j][1] -= minFreq;
if (encoded1[i][1] == 0)
++i;
if (encoded2[j][1] == 0)
++j;
}

return ans;
}
};
``````

## JAVA

``````class Solution {
public List<List<Integer>> findRLEArray(int[][] encoded1, int[][] encoded2) {
List<List<Integer>> ans = new ArrayList<>();
int i = 0; // encoded1's index
int j = 0; // encodes2's index

while (i < encoded1.length && j < encoded2.length) {
final int mult = encoded1[i][0] * encoded2[j][0];
final int minFreq = Math.min(encoded1[i][1], encoded2[j][1]);
if (!ans.isEmpty() && mult == ans.get(ans.size() - 1).get(0))
ans.get(ans.size() - 1).set(1, ans.get(ans.size() - 1).get(1) + minFreq);
else
encoded1[i][1] -= minFreq;
encoded2[j][1] -= minFreq;
if (encoded1[i][1] == 0)
++i;
if (encoded2[j][1] == 0)
++j;
}

return ans;
}
}
``````

## Python

``````class Solution:
def findRLEArray(self, encoded1: List[List[int]],
encoded2: List[List[int]]) -> List[List[int]]:
ans = []
i = 0  # encoded1's index
j = 0  # encoded2's index

while i < len(encoded1) and j < len(encoded2):
mult = encoded1[i][0] * encoded2[j][0]
minFreq = min(encoded1[i][1], encoded2[j][1])
if ans and mult == ans[-1][0]:
ans[-1][1] += minFreq
else:
ans.append([mult, minFreq])
encoded1[i][1] -= minFreq
encoded2[j][1] -= minFreq
if encoded1[i][1] == 0:
i += 1
if encoded2[j][1] == 0:
j += 1

return ans
``````