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] = [vali, freqi] describes the ith segment of repeated numbers in nums where vali is the value that is repeated freqi times.
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:
encoded1 and encoded2 into the full arrays nums1 and nums2 respectively.prodNums of length nums1.length and set prodNums[i] = nums1[i] * nums2[i].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] = [vali, freqi] describes the ith segment of nums1, and each encoded2[j] = [valj, freqj] describes the jth 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.
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 run-length 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 run-length encoded array [[2,3],[6,1],[9,2]].
Constraints:
1 <= encoded1.length, encoded2.length <= 105encoded1[i].length == 2encoded2[j].length == 21 <= vali, freqi <= 104 for each encoded1[i].1 <= valj, freqj <= 104 for each encoded2[j].encoded1 and encoded2 represent are the same length.Problem Overview: You are given two arrays encoded using run-length encoding (RLE). Each element is stored as [value, frequency], meaning the value repeats multiple times. The task is to compute the element-wise product of the fully expanded arrays and return the result in run-length encoded form.
Approach 1: Decompress Then Multiply (Brute Force) (Time: O(N + M), Space: O(N + M))
The most straightforward idea is to fully expand both encoded arrays into their original forms. Iterate through each [value, frequency] pair and append the value frequency times into a new array. Once both arrays are decompressed, compute the element-wise product and then run-length encode the result again by grouping consecutive identical values.
This method works but defeats the purpose of run-length encoding. If frequencies are large, the decompressed arrays can be huge, causing unnecessary memory usage. The approach mainly helps verify correctness before implementing the optimal solution.
Approach 2: Two Pointers on Encoded Segments (Optimal) (Time: O(n + m), Space: O(1) excluding output)
The key insight is that you never need to decompress the arrays. Each encoded pair represents a contiguous segment of identical values. Instead of expanding them, process segments directly using a two pointers technique.
Maintain one pointer for each encoded array. At every step, multiply the current values from both segments. The number of elements contributing to the product is the minimum of their remaining frequencies. Append a new segment [product, minFreq] to the result.
After producing this segment, reduce the frequency of both segments by minFreq. If one segment is exhausted, move its pointer to the next pair. Continue until one array is fully processed. While appending to the result, merge with the previous segment if the product value is the same to keep the output properly run-length encoded.
This approach processes each encoded segment once. No large intermediate arrays are created, which keeps memory usage minimal. The pattern is similar to merging intervals or scanning sorted lists and commonly appears in problems involving compressed data structures or array segment processing.
Recommended for interviews: Interviewers expect the two-pointer segment processing approach. It shows you recognize that decompression is unnecessary and can operate directly on encoded data. Mentioning the brute force idea first demonstrates understanding of the problem, but implementing the optimal two pointers solution shows strong algorithmic judgment and efficiency awareness.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Decompress Then Multiply | O(N + M) | O(N + M) | Useful for understanding the problem or when input sizes are small. |
| Two Pointers on Encoded Segments | O(n + m) | O(1) | Optimal approach. Works directly on run-length encoded segments without decompression. |
PRODUCT OF TWO RUN-LENGTH ENCODED ARRAYS | PYTHON | LEETCODE # 1868 • Cracking FAANG • 5,028 views views
Watch 6 more video solutions →Practice Product of Two Run-Length Encoded Arrays with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor