We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Product of Two Run-Length Encoded Arrays

Number: 2019

Difficulty: Medium

Paid? Yes

Companies: Meta, Yandex

Problem Description

Given two run-length encoded arrays, encoded1 and encoded2, each representing full arrays where each element is defined by a pair [value, frequency], compute the element-wise product of the two underlying arrays and then compress the result back into a run-length encoded format with the minimum possible length.

Key Insights

  • Use a two-pointer technique to process both encoded arrays simultaneously without expanding them to the full arrays.
  • Multiply corresponding segments of values and determine the overlapping frequency (minimum of the current frequencies).
  • Maintain optimal compression by merging consecutive segments having the same product.
  • Reduce frequencies and move pointers forward as segments get fully used.

Space and Time Complexity

Time Complexity: O(n + m), where n and m are the lengths of encoded1 and encoded2, respectively. Space Complexity: O(n + m) for the output in the worst case, though typically the output will be compressed and smaller.

Solution

We use a two-pointer approach to iterate over the two run-length encoded arrays simultaneously. At each step, we take the minimum frequency from the current segments and compute the product of their values. We then append or merge this product to the result run-length encoded array. After processing the overlapping segment, we subtract the used frequency from both segments and move the pointer forward when a segment is exhausted. This avoids the costly operation of expanding the arrays and ensures an optimal and compressed result.

Code Solutions

# Python implementation with line-by-line comments
def findRLEProduct(encoded1, encoded2):
    result = []  # To store the resulting run-length encoded array
    i, j = 0, 0  # Pointers for encoded1 and encoded2
    
    while i < len(encoded1) and j < len(encoded2):
        val1, freq1 = encoded1[i]
        val2, freq2 = encoded2[j]
        # Determine the number of elements to process for the current segments
        common = min(freq1, freq2)
        product = val1 * val2
        
        # Merge with the last segment if the product is the same
        if result and result[-1][0] == product:
            result[-1][1] += common
        else:
            result.append([product, common])
        
        # Update frequencies after processing common length
        encoded1[i][1] -= common
        encoded2[j][1] -= common
        
        # Move pointer i if its current frequency is all used
        if encoded1[i][1] == 0:
            i += 1
        # Similarly move pointer j if its current frequency is all used
        if encoded2[j][1] == 0:
            j += 1
    return result

# Example usage:
encoded1 = [[1,3],[2,1],[3,2]]
encoded2 = [[2,3],[3,3]]
print(findRLEProduct(encoded1, encoded2))  # Output: [[2,3],[6,1],[9,2]]
← Back to All Questions