1868. Product of Two Run-Length Encoded Arrays - Detailed Explanation

Problem Statement

You are given two run-length encoded arrays, encoded1 and encoded2. Each array consists of subarrays of the form [value, frequency], which represent a sequence where the number value appears consecutively frequency times. It is guaranteed that the total number of elements represented by encoded1 is equal to that represented by encoded2.

Your task is to compute the element-wise product of the two decoded arrays and then return the result in run-length encoded form. When encoding the result, if consecutive segments have the same product, they must be merged into one segment.

Example 1

• Input:
  encoded1 = [[1, 3], [2, 1]]
encoded2 = [[6, 2], [3, 2]]
• Output:
  [[6, 2], [3, 1], [6, 1]]
• Explanation:
  • Decoding the arrays:
    encoded1 decodes to [1, 1, 1, 2]
encoded2 decodes to [6, 6, 3, 3]
  • Element-wise product: [1*6, 1*6, 1*3, 2*3] → [6, 6, 3, 6]
  • Run-length encoding the product:
    There are two 6's, then one 3, then one 6 → [[6, 2], [3, 1], [6, 1]]

Example 2

• Input:
  encoded1 = [[1, 2], [3, 3]]
encoded2 = [[2, 4], [5, 1]]
• Output:
  [[2, 2], [6, 2], [15, 1]]
• Explanation:
  • Decoding the arrays:
    encoded1 decodes to [1, 1, 3, 3, 3]
encoded2 decodes to [2, 2, 2, 2, 5]
  • Element-wise product: [1*2, 1*2, 3*2, 3*2, 3*5] → [2, 2, 6, 6, 15]
  • Run-length encoding: two 2's, then two 6's, and one 15 → [[2, 2], [6, 2], [15, 1]]

Example 3

• Input:
  encoded1 = [[2, 5]]
encoded2 = [[3, 5]]
• Output:
  [[6, 5]]
• Explanation:
  • Decoding the arrays:
    Both decode to five elements: [2, 2, 2, 2, 2] and [3, 3, 3, 3, 3]
  • Element-wise product: each pair gives 2 * 3 = 6 → [6, 6, 6, 6, 6]
  • Run-length encoding: one segment with product 6 repeated 5 times → [[6, 5]]

Constraints:

• 1 <= encoded1.length, encoded2.length <= 10^4
• Each element of encoded1 and encoded2 is of the form [value, frequency] where 1 <= value, frequency <= 10^4.
• The total frequencies (i.e., the decoded array length) of encoded1 and encoded2 are equal.

Hints

1. Hint 1:
   Rather than decoding the entire arrays (which could be very large), simulate the process using two pointers—one for each encoded array. At each step, determine the minimum frequency available between the two current segments and process that many elements in one go.

2. Hint 2:
   When building the output, if the product for the current group is the same as that of the previous group in your result, merge them by adding the frequencies. This helps in maintaining a proper run-length encoded format without redundant segments.

Approach 1: Two-Pointer Simulation (Optimal Solution)

Explanation

• Initialization:
  Start with two pointers, i for encoded1 and j for encoded2. Create an empty result list to store the final run-length encoded product.

• Processing Segments:
  While both pointers are valid:

  1. Retrieve the current segments:
     current1 = [val1, freq1] from encoded1[i] and current2 = [val2, freq2] from encoded2[j].
  2. Compute count = min(freq1, freq2). This represents how many elements in the current segments can be processed together.
  3. Calculate the product: product = val1 * val2.
  4. Append the [product, count] pair to the result. If the last segment in the result already has the same product, simply add count to its frequency.
  5. Deduct count from both freq1 and freq2. If either becomes zero, move the corresponding pointer to the next segment.

• Termination:
  Continue until both encoded arrays are completely processed.

Visual Example

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

1. Initialization:

   • i = 0, j = 0, result = []

2. Iteration 1:

   • Current segments: [1, 3] and [6, 2]
   • count = min(3, 2) = 2
   • product = 1 * 6 = 6
   • Append [6, 2] to result → result = [[6, 2]]
   • Update segments: [1, 3-2] becomes [1, 1] and [6, 2-2] becomes [6, 0]
   • Move pointer j to 1.

3. Iteration 2:

   • Now i = 0 (segment [1, 1]) and j = 1 (segment [3, 2])
   • count = min(1, 2) = 1
   • product = 1 * 3 = 3
   • Append [3, 1] to result → result = [[6, 2], [3, 1]]
   • Update segments: [1, 1-1] becomes [1, 0] and [3, 2-1] becomes [3, 1]
   • Move pointer i to 1.

4. Iteration 3:

   • Now i = 1 (segment [2, 1]) and j = 1 (segment [3, 1])
   • count = min(1, 1) = 1
   • product = 2 * 3 = 6
   • Since the last segment in result is [3, 1] (with product 3), append [6, 1] → result = [[6, 2], [3, 1], [6, 1]]

5. Final Result:
   The output is [[6, 2], [3, 1], [6, 1]].

Code in Python