1868. Product of Two Run-Length Encoded Arrays

Problem Statement

link: LeetCode.cn LeetCode 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.

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 can be calculated using the following steps:

Expand both encoded1 and encoded2 into the full arrays nums1 and nums2 respectively. Create a new array prodNums of length nums1.length and set prodNums[i] = nums1[i] * nums2[i]. Compress 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:

Input: encoded1 = [[1,3],[2,3]], encoded2 = [[6,3],[3,3]] Output: [[6,6]]

Input: encoded1 = [[1,3],[2,1],[3,2]], encoded2 = [[2,3],[3,3]] Output: [[2,3],[6,1],[9,2]]

Constraints: 1 <= encoded1.length, encoded2.length <= 10^5 encoded1[i].length == 2 encoded2[j].length == 2 1 <= vali, freqi <= 10^4 for each encoded1[i]. 1 <= valj, freqj <= 10^4 for each encoded2[j]. The full arrays that encoded1 and encoded2 represent are the same length.

Solution Approach

The solution uses two pointers to iterate through the run-length encoded arrays, multiplying corresponding values and managing frequency counts, while merging results into a compressed run-length encoded format.

Algorithm

1. Two-Pointer Technique: The algorithm uses two pointers to traverse the run-length encoded arrays simultaneously, comparing and processing the segments from both arrays.
2. Frequency Management: It manages the remaining frequencies of segments (remain1 and remain2) to handle cases where segment lengths differ, ensuring that all values are processed correctly.
3. Merging and Compression: As it processes segments, the algorithm multiplies values from both arrays and merges the results into a compressed run-length encoded format, combining consecutive segments with the same value to minimize the output size.

Complexity

time complexity: O(n1 + n2) space complexity: O(n)

Implement

    class Solution:
    def findRLEArray(self, encoded1: List[List[int]], encoded2: List[List[int]]) -> List[List[int]]:
        res = []
        n1, n2 = len(encoded1), len(encoded2)
        p1 = p2 = 0
        remain1 = remain2 = 0
        while p1 < n1 and p2 < n2:
            freq1 = remain1 if remain1 > 0 else encoded1[p1][1]
            freq2 = remain2 if remain2 > 0 else encoded2[p2][1]
            min_freq = min(freq1, freq2)
            mul = encoded1[p1][0] * encoded2[p2][0]
            if res and res[-1][0] == mul:
                res[-1][1] += min_freq
            else:
                res.append([mul, min_freq])
            if freq1 > freq2:
                remain1 = freq1 - freq2
                remain2 = 0
                p2 += 1
            elif freq1 < freq2:
                remain1 = 0
                remain2 = freq2 - freq1
                p1 += 1
            else:
                remain1 = remain2 = 0
                p1 += 1
                p2 += 1
        return res
    

    
    

Twitter  facebook  Email