[Medium] 1868. Product of Two Run-Length Encoded Arrays

Difficulty: Medium
Category: Run-Length Encoding, Two Pointers, Array Processing

Run-length encoding is a compression algorithm that allows for an integer array nums with many segments of repeated numbers to be represented by a (generally smaller) 2D array encoded. Each encoded[i] = [vali, freqi] describes the ith segment of repeated numbers in nums where vali is the value that is repeated freqi 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 is a run-length encoded array that represents the product of nums1 and nums2.

Given two run-length encoded arrays encoded1 and encoded2, both of length n, return the product of encoded1 and encoded2.

Note: Compression does not affect the product, and you can assume that the product of nums1 and nums2 does not exceed 10^9.

Examples

Example 1:

Input: encoded1 = [[1,3],[2,3]], encoded2 = [[6,3],[3,3]]
Output: [[6,6]]
Explanation: encoded1 represents [1,1,1,2,2,2] and encoded2 represents [6,6,6,3,3,3].
The product is [6,6,6,6,6,6], which is represented by [[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 represents [1,1,1,2,3,3] and encoded2 represents [2,2,2,3,3,3].
The product is [2,2,2,6,9,9], which is represented by [[2,3],[6,1],[9,2]].

Constraints

2 <= encoded1.length, encoded2.length <= 10^5
encoded1[i].length == encoded2[j].length == 2
1 <= vali, freqi <= 10^4

Thinking Process

The key insight is to process both encoded arrays simultaneously using two pointers, computing the product of corresponding elements and merging consecutive segments with the same value.

Algorithm:

Use two pointers i and j to traverse both encoded arrays
At each step, take the minimum frequency between the current segments
Compute the product of the values and the minimum frequency
If the result array is not empty and the last segment has the same value, merge frequencies
Otherwise, add a new segment
Decrease frequencies and advance pointers when segments are exhausted

Common Approaches

Typical techniques for this pattern:

Approach	Time	Space	Notes
Opposite ends (this problem)	O(n)	O(1)	Sorted array pair search, reversal
Slow / fast pointers	O(n)	O(1)	Linked list middle, cycle detection
Same-direction chase	O(n)	O(1)	Remove duplicates in-place
Sliding window (variable)	O(n)	O(1)	Subarray with constraint

Solution

class Solution {
public:
    vector<vector<int>> findRLEArray(vector<vector<int>>& encoded1, vector<vector<int>>& encoded2) {
        int i = 0, j = 0;
        vector<vector<int>> rtn;
        while(i < (int)encoded1.size() && j < (int)encoded2.size()) {
            int freq = min(encoded1[i][1], encoded2[j][1]);
            int val = encoded1[i][0] * encoded2[j][0];
            encoded1[i][1] -= freq;
            encoded2[j][1] -= freq;
            if(!rtn.empty() && rtn.back()[0] == val) {
                rtn.back()[1] += freq;
            } else {
                rtn.push_back({val, freq});
            }
            if(encoded1[i][1] == 0) i++;
            if(encoded2[j][1] == 0) j++;
        }
        return rtn;
    }
};

Solution Explanation

The key insight is to process both encoded arrays simultaneously using two pointers, computing the product of corresponding elements and merging consecutive segments with the same value.

See Complexity below for time and space analysis.

Explanation

Step-by-Step Process:

Initialize pointers: i = 0, j = 0 to track positions in both arrays
Process segments: While both arrays have unprocessed segments:
- Take minimum frequency: freq = min(encoded1[i][1], encoded2[j][1])
- Compute product: val = encoded1[i][0] * encoded2[j][0]
- Decrease frequencies: Subtract freq from both current segments
Merge or add segment:
- If result is empty or last segment has different value: add new segment
- If last segment has same value: merge frequencies
Advance pointers: Move to next segment when current frequency reaches 0

Example Walkthrough:

For encoded1 = [[1,3],[2,3]] and encoded2 = [[6,3],[3,3]]:

Step 1: min(3,3) = 3, val = 1*6 = 6, add [6,3]
Step 2: min(3,3) = 3, val = 2*3 = 6, merge with previous: [6,6]
Result: [[6,6]]

Complexity

Time Complexity: O(n + m) where n and m are the lengths of the encoded arrays

Each segment is processed exactly once
Merging operations are O(1)

Space Complexity: O(n + m) for the result array

In worst case, no segments can be merged

References

LC 1868: Product of Two Run-Length Encoded Arrays on LeetCode
LeetCode Discuss — LC 1868: Product of Two Run-Length Encoded Arrays
LeetCode Editorial (may require premium)

Common Mistakes

Skipping edge cases (empty input, single element, boundaries).
Off-by-one errors in loops and index ranges.
Forgetting to handle the case when no valid answer exists.

Key Takeaways

Two-pointer technique: Efficiently process both arrays simultaneously
Frequency management: Always consume the minimum frequency to avoid gaps
Segment merging: Combine consecutive segments with same values to maintain compression
In-place modification: Modify input arrays to track remaining frequencies

This approach efficiently computes the product while maintaining the run-length encoded format and optimal compression.

Robina Li