LeetCode 1868 - Product of Two Run-Length Encoded Arrays
This problem asks us to multiply two arrays that are already stored in run-length encoded form, without fully expanding them into normal arrays. A run-length encoded array stores consecutive repeated values compactly.
Difficulty: 🟡 Medium
Topics: Array, Two Pointers
Solution
Problem Understanding
This problem asks us to multiply two arrays that are already stored in run-length encoded form, without fully expanding them into normal arrays.
A run-length encoded array stores consecutive repeated values compactly. Instead of explicitly storing every element, it stores pairs of:
- the value
- how many times it appears consecutively
For example:
[5,5,5,5,2,2]
becomes:
[[5,4],[2,2]]
The task is to compute the element-wise product of two such encoded arrays.
If:
nums1 = [1,1,1,2,2,2]
nums2 = [6,6,6,3,3,3]
then the product array is:
[6,6,6,6,6,6]
which compresses into:
[[6,6]]
The important detail is that the final output must also be run-length encoded with the minimum possible length. That means adjacent segments with the same product value must be merged together.
The constraints are large:
encoded1.lengthandencoded2.lengthcan each be up to10^5- frequencies can also be large
- the expanded arrays may be enormous
This immediately tells us that fully expanding the arrays is not feasible. Even though the encoded representation is small, the decompressed arrays could contain billions of elements.
The problem guarantees that both expanded arrays have the same total length, which simplifies synchronization between the two encodings.
Several edge cases are important:
- Adjacent product segments may need to be merged
- One segment may partially overlap multiple segments in the other array
- Entire arrays may collapse into a single encoded segment
- Frequencies may become zero as we consume portions of segments
- The optimal solution must avoid decompression entirely
Approaches
Brute Force Approach
The most straightforward solution is to:
- Expand both encoded arrays into their full forms
- Multiply corresponding elements
- Compress the resulting array back into run-length encoding
This approach is conceptually simple and clearly correct because it directly follows the problem definition.
For example:
encoded1 = [[1,3],[2,2]]
encoded2 = [[4,3],[5,2]]
would expand into:
nums1 = [1,1,1,2,2]
nums2 = [4,4,4,5,5]
Then:
product = [4,4,4,10,10]
Finally compress:
[[4,3],[10,2]]
The issue is scalability. Frequencies can be extremely large, so the expanded arrays may contain far too many elements to fit in memory or process efficiently.
Optimal Approach
The key observation is that we never actually need the fully expanded arrays.
Each encoded segment already tells us:
- which value repeats
- how many times it repeats
We can process the two encodings directly using two pointers.
At any moment:
- one pointer references the current segment in
encoded1 - another pointer references the current segment in
encoded2
The current product value is:
value1 * value2
The number of positions this product applies to is:
min(freq1, freq2)
because the shorter remaining segment determines how long the overlap lasts.
After processing that overlap:
- subtract the used frequency from both segments
- advance whichever segment becomes exhausted
This allows us to process the arrays in compressed form only, achieving linear complexity in the number of encoded segments.
We also merge adjacent output segments when their product values match, ensuring minimal compression.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(N) | O(N) | Expands both arrays fully, impractical for large frequencies |
| Optimal | O(m + n) | O(m + n) | Processes encoded segments directly using two pointers |
Here:
Nis the size of the expanded arraysmandnare the lengths of the encoded arrays
Algorithm Walkthrough
Optimal Two Pointer Algorithm
- Initialize two pointers, one for each encoded array.
Pointer i tracks the current segment in encoded1, and pointer j tracks the current segment in encoded2.
2. Read the current values and frequencies.
Suppose:
encoded1[i] = [value1, freq1]
encoded2[j] = [value2, freq2]
The current product value is:
product = value1 * value2
- Determine how many positions this product spans.
Since both segments repeat their values consecutively, the overlap length is:
overlap = min(freq1, freq2)
This means the product value repeats overlap times.
4. Add the product segment to the result.
If the previous output segment already has the same product value, merge them by increasing its frequency.
Otherwise, append a new segment. 5. Reduce the remaining frequencies.
Since we used overlap positions:
freq1 -= overlap
freq2 -= overlap
- Advance exhausted segments.
If freq1 becomes zero, increment i.
If freq2 becomes zero, increment j.
7. Continue until both encoded arrays are fully processed.
Why it works
The algorithm works because run-length encoding partitions the original arrays into consecutive constant-value ranges.
At every step, the current segments define identical values across contiguous ranges. The overlap length represents the largest range where both current values remain active simultaneously.
By consuming overlaps incrementally, we exactly simulate element-wise multiplication without decompression. Since every position is processed once and adjacent equal products are merged immediately, the final encoding is guaranteed to be minimal and correct.
Python Solution
from typing import List
class Solution:
def findRLEArray(
self,
encoded1: List[List[int]],
encoded2: List[List[int]]
) -> List[List[int]]:
i = 0
j = 0
result = []
while i < len(encoded1) and j < len(encoded2):
value1, freq1 = encoded1[i]
value2, freq2 = encoded2[j]
product = value1 * value2
overlap = min(freq1, freq2)
if result and result[-1][0] == product:
result[-1][1] += overlap
else:
result.append([product, overlap])
encoded1[i][1] -= overlap
encoded2[j][1] -= overlap
if encoded1[i][1] == 0:
i += 1
if encoded2[j][1] == 0:
j += 1
return result
The implementation follows the two pointer strategy directly.
The pointers i and j track the current segments in both encoded arrays. At each iteration, the algorithm computes:
- the current product value
- the overlap frequency
The overlap is the number of elements that can be processed before at least one segment is exhausted.
The result compression is handled immediately during construction. If the new product matches the last stored product, the frequencies are merged instead of appending a new segment. This guarantees minimal encoding length without needing a second compression pass.
The frequencies inside the input arrays are reduced in place as overlaps are consumed. Once a segment frequency reaches zero, the corresponding pointer advances to the next segment.
The loop continues until all segments are fully processed.
Go Solution
func findRLEArray(encoded1 [][]int, encoded2 [][]int) [][]int {
i := 0
j := 0
result := [][]int{}
for i < len(encoded1) && j < len(encoded2) {
value1 := encoded1[i][0]
freq1 := encoded1[i][1]
value2 := encoded2[j][0]
freq2 := encoded2[j][1]
product := value1 * value2
overlap := freq1
if freq2 < overlap {
overlap = freq2
}
if len(result) > 0 && result[len(result)-1][0] == product {
result[len(result)-1][1] += overlap
} else {
result = append(result, []int{product, overlap})
}
encoded1[i][1] -= overlap
encoded2[j][1] -= overlap
if encoded1[i][1] == 0 {
i++
}
if encoded2[j][1] == 0 {
j++
}
}
return result
}
The Go implementation mirrors the Python solution closely.
Slices are used for both the encoded arrays and the result. Since Go does not provide a built-in min function for integers, the overlap is computed manually using a simple comparison.
The algorithm mutates the input frequencies directly, just like the Python version. This avoids additional memory allocation for tracking remaining counts.
Integer overflow is not a concern here because the maximum product is:
10^4 * 10^4 = 10^8
which fits comfortably inside Go's int type.
Worked Examples
Example 1
Input:
encoded1 = [[1,3],[2,3]]
encoded2 = [[6,3],[3,3]]
Expanded arrays:
[1,1,1,2,2,2]
[6,6,6,3,3,3]
Step-by-step trace
| Step | Segment 1 | Segment 2 | Product | Overlap | Result |
|---|---|---|---|---|---|
| 1 | [1,3] | [6,3] | 6 | 3 | [[6,3]] |
| 2 | [2,3] | [3,3] | 6 | 3 | [[6,6]] |
Final output:
[[6,6]]
Notice that the second product segment also equals 6, so it merges with the previous segment.
Example 2
Input:
encoded1 = [[1,3],[2,1],[3,2]]
encoded2 = [[2,3],[3,3]]
Expanded arrays:
[1,1,1,2,3,3]
[2,2,2,3,3,3]
Step-by-step trace
| Step | Segment 1 | Segment 2 | Product | Overlap | Result |
|---|---|---|---|---|---|
| 1 | [1,3] | [2,3] | 2 | 3 | [[2,3]] |
| 2 | [2,1] | [3,3] | 6 | 1 | [[2,3],[6,1]] |
| 3 | [3,2] | [3,2] | 9 | 2 | [[2,3],[6,1],[9,2]] |
Final output:
[[2,3],[6,1],[9,2]]
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(m + n) | Each encoded segment is processed once |
| Space | O(m + n) | Result may contain up to all combined segment transitions |
The algorithm never expands the arrays, which is the crucial optimization.
Each segment in encoded1 and encoded2 is visited at most once. Every iteration consumes at least one segment completely, guaranteeing linear progress.
The result array can contain at most m + n - 1 segments in the worst case, so the output size dominates the auxiliary space usage.
Test Cases
from typing import List
class Solution:
def findRLEArray(
self,
encoded1: List[List[int]],
encoded2: List[List[int]]
) -> List[List[int]]:
i = 0
j = 0
result = []
while i < len(encoded1) and j < len(encoded2):
value1, freq1 = encoded1[i]
value2, freq2 = encoded2[j]
product = value1 * value2
overlap = min(freq1, freq2)
if result and result[-1][0] == product:
result[-1][1] += overlap
else:
result.append([product, overlap])
encoded1[i][1] -= overlap
encoded2[j][1] -= overlap
if encoded1[i][1] == 0:
i += 1
if encoded2[j][1] == 0:
j += 1
return result
sol = Solution()
# Example 1 from problem statement
assert sol.findRLEArray(
[[1,3],[2,3]],
[[6,3],[3,3]]
) == [[6,6]]
# Example 2 from problem statement
assert sol.findRLEArray(
[[1,3],[2,1],[3,2]],
[[2,3],[3,3]]
) == [[2,3],[6,1],[9,2]]
# Entire result merges into one segment
assert sol.findRLEArray(
[[2,2],[3,2]],
[[3,2],[2,2]]
) == [[6,4]]
# Single segment arrays
assert sol.findRLEArray(
[[5,10]],
[[2,10]]
) == [[10,10]]
# Alternating overlap boundaries
assert sol.findRLEArray(
[[1,1],[2,1],[3,1]],
[[4,3]]
) == [[4,1],[8,1],[12,1]]
# Multiple partial consumptions
assert sol.findRLEArray(
[[1,5]],
[[2,2],[3,2],[4,1]]
) == [[2,2],[3,2],[4,1]]
# Adjacent equal products created from different pairs
assert sol.findRLEArray(
[[1,2],[2,2]],
[[6,2],[3,2]]
) == [[6,4]]
# Large frequencies
assert sol.findRLEArray(
[[10000,10000]],
[[10000,10000]]
) == [[100000000,10000]]
# One segment split across many segments
assert sol.findRLEArray(
[[2,8]],
[[1,3],[2,3],[3,2]]
) == [[2,3],[4,3],[6,2]]
# Exact exhaustion alignment
assert sol.findRLEArray(
[[1,2],[2,2]],
[[3,2],[4,2]]
) == [[3,2],[8,2]]
| Test | Why |
|---|---|
| Example 1 | Validates merging adjacent equal products |
| Example 2 | Validates normal multi-segment processing |
| Entire result merges into one segment | Ensures compression is minimal |
| Single segment arrays | Simplest non-trivial case |
| Alternating overlap boundaries | Tests frequent pointer advancement |
| Multiple partial consumptions | Tests one segment spanning several others |
| Adjacent equal products created from different pairs | Verifies merge logic correctness |
| Large frequencies | Confirms scalability and integer handling |
| One segment split across many segments | Tests repeated partial overlap consumption |
| Exact exhaustion alignment | Tests simultaneous pointer advancement |
Edge Cases
Adjacent product segments produce the same value
Different input segment pairs can generate identical products consecutively.
For example:
encoded1 = [[1,2],[2,2]]
encoded2 = [[6,2],[3,2]]
Both produce product 6.
A buggy implementation might append:
[[6,2],[6,2]]
instead of merging them into:
[[6,4]]
The implementation handles this by checking the last result segment before appending a new one.
One segment overlaps multiple segments
A single segment in one array may partially overlap several segments in the other array.
For example:
encoded1 = [[5,10]]
encoded2 = [[1,3],[2,4],[3,3]]
The first segment of encoded1 must be consumed gradually across multiple segments from encoded2.
A naive implementation may incorrectly advance pointers too early. The algorithm avoids this by subtracting only the overlap amount and advancing pointers only when a frequency reaches zero.
Simultaneous segment exhaustion
Sometimes both current segments finish at exactly the same time.
Example:
[1,3]
[2,3]
Both frequencies become zero after processing overlap 3.
An incorrect implementation might advance only one pointer, causing repeated processing or infinite loops.
The solution independently checks both frequencies after subtraction and advances both pointers when necessary.