Problem Description

This problem asks you to find the product of two run-length encoded arrays.

Run-length encoding is a compression technique where consecutive repeated numbers in an array are represented as [value, frequency] pairs. For example, the array [1,1,1,2,2,2,2,2] can be encoded as [[1,3],[2,5]], meaning "three 1's followed by five 2's".

Given two run-length encoded arrays encoded1 and encoded2 that represent arrays of the same length, you need to:

1. Conceptually expand both encoded arrays back to their full forms (though you shouldn't actually do this in implementation)
2. Multiply the corresponding elements at each position
3. Compress the resulting product array back into run-length encoded format

For example:

• If encoded1 = [[1,3],[2,5]] represents [1,1,1,2,2,2,2,2]
• And encoded2 = [[3,3],[4,5]] represents [3,3,3,4,4,4,4,4]
• The element-wise product would be [3,3,3,8,8,8,8,8]
• Which compresses to [[3,3],[8,5]]

The key insight is that you don't need to fully expand the arrays. Instead, you can work directly with the encoded format by:

• Using two pointers to track positions in both encoded arrays
• Taking the minimum frequency between current segments to determine how many products to compute
• Multiplying the values and tracking the frequency
• Merging consecutive segments with the same product value
• Advancing pointers when a segment is exhausted

The solution must return the compressed run-length encoded array with the minimum possible length (meaning consecutive segments with the same value should be merged).

Intuition

The naive approach would be to fully expand both encoded arrays, multiply them element by element, and then compress the result. However, this would be inefficient in terms of both time and space, especially when dealing with large frequencies.

The key observation is that we can work directly with the compressed format. Think of the encoded arrays as describing "segments" or "blocks" of repeated values. When we multiply two arrays element-wise, we're essentially aligning these segments and multiplying their values.

Consider how segments align: if encoded1 has a segment [val1, freq1] and encoded2 has a segment [val2, freq2], these segments might not perfectly align. One segment might "span" multiple segments from the other array. For example:

• encoded1 = [[2, 6]] represents [2,2,2,2,2,2]
• encoded2 = [[3, 4], [4, 2]] represents [3,3,3,3,4,4]

Here, the segment [2, 6] from encoded1 overlaps with both segments from encoded2.

The insight is to process these segments in "chunks" by taking the minimum frequency at each step. We maintain pointers for both arrays and at each step:

1. Take the smaller frequency between the current segments - this tells us how many elements we can process together
2. Multiply the values to get the product value for this chunk
3. Decrease the frequencies of both current segments by the amount we processed
4. When a segment's frequency reaches zero, move to the next segment in that array

This way, we're essentially "consuming" both arrays in parallel, always processing the maximum number of elements we can handle at once without needing to split a multiplication operation.

To maintain the minimum length requirement, whenever we add a new [product, frequency] pair to our result, we check if it has the same value as the last pair we added. If so, we merge them by adding the frequencies instead of creating a new entry.

Learn more about Two Pointers patterns.

Solution Approach

The solution uses a two-pointer approach to process both encoded arrays simultaneously without expanding them.

Algorithm Steps:

1. Initialize variables:

   • ans - result list to store the run-length encoded product
   • j = 0 - pointer for encoded2 (we iterate through encoded1 directly)

2. Iterate through each segment in encoded1:

   • For each segment [vi, fi] in encoded1, we need to multiply vi with corresponding values from encoded2
   • Use a while loop to process all fi elements of the current segment

3. Process segments in chunks:

   • Calculate f = min(fi, encoded2[j][1]) - this is the number of elements we can process together
   • Compute the product: v = vi * encoded2[j][0]
   • This gives us a chunk of f elements with value v

4. Merge consecutive segments with same value:

   • If ans is not empty and the last segment has the same value v, merge by adding frequencies: ans[-1][1] += f
   • Otherwise, append a new segment: ans.append([v, f])

5. Update frequencies and pointers:

   • Decrease fi by f (elements processed from current encoded1 segment)
   • Decrease encoded2[j][1] by f (elements processed from current encoded2 segment)
   • If encoded2[j][1] becomes 0, move to next segment: j += 1

Example walkthrough:

encoded1 = [[1,3], [2,2]]  # represents [1,1,1,2,2]
encoded2 = [[3,2], [4,3]]  # represents [3,3,4,4,4]

Step 1: vi=1, fi=3, j=0
  - f = min(3, 2) = 2
  - v = 1 * 3 = 3
  - ans = [[3, 2]]
  - fi = 1, encoded2[0][1] = 0, j = 1

Step 2: vi=1, fi=1, j=1
  - f = min(1, 3) = 1
  - v = 1 * 4 = 4
  - ans = [[3, 2], [4, 1]]
  - fi = 0, encoded2[1][1] = 2

Step 3: vi=2, fi=2, j=1
  - f = min(2, 2) = 2
  - v = 2 * 4 = 8
  - ans = [[3, 2], [4, 1], [8, 2]]

Result: [[3,2], [4,1], [8,2]]  # represents [3,3,4,8,8]

The time complexity is O(m + n) where m and n are the lengths of the encoded arrays, as we process each segment exactly once. The space complexity is O(1) if we don't count the output array.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach:

Input:

• encoded1 = [[2,3], [3,2]] which represents [2,2,2,3,3]
• encoded2 = [[5,2], [1,3]] which represents [5,5,1,1,1]

Expected output: The product [10,10,2,3,3] encoded as [[10,2], [2,1], [3,2]]

Step-by-step execution:

Initial state:

• ans = [] (result array)
• j = 0 (pointer for encoded2)
• Start processing first segment of encoded1: [2,3]

Iteration 1 - Processing segment [2,3] from encoded1:

• vi = 2, fi = 3 (value and frequency from encoded1)
• encoded2[j] = [5,2] (current segment in encoded2)
• f = min(3, 2) = 2 (can process 2 elements)
• v = 2 * 5 = 10 (product value)
• Add [10, 2] to ans → ans = [[10,2]]
• Update: fi = 3-2 = 1, encoded2[0][1] = 2-2 = 0
• Since encoded2[0][1] = 0, increment j = 1

Iteration 1 continued - Still processing [2,3]:

• fi = 1 (remaining frequency from current encoded1 segment)
• encoded2[j] = [1,3] (moved to next segment)
• f = min(1, 3) = 1 (can process 1 element)
• v = 2 * 1 = 2 (product value)
• Add [2, 1] to ans → ans = [[10,2], [2,1]]
• Update: fi = 1-1 = 0, encoded2[1][1] = 3-1 = 2
• fi = 0, so move to next segment in encoded1

Iteration 2 - Processing segment [3,2] from encoded1:

• vi = 3, fi = 2 (value and frequency from encoded1)
• encoded2[j] = [1,2] (current segment with remaining frequency)
• f = min(2, 2) = 2 (can process 2 elements)
• v = 3 * 1 = 3 (product value)
• Add [3, 2] to ans → ans = [[10,2], [2,1], [3,2]]
• Update: fi = 2-2 = 0, encoded2[1][1] = 2-2 = 0

Final result: [[10,2], [2,1], [3,2]]

This represents the array [10,10,2,3,3], which is indeed the element-wise product of [2,2,2,3,3] and [5,5,1,1,1].

The key insight demonstrated here is how we "consume" both arrays simultaneously using the minimum frequency at each step, avoiding the need to expand the arrays while still correctly computing the product.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n + m) where n is the length of encoded1 and m is the length of encoded2.

The algorithm iterates through each element in encoded1 once using the outer loop. For each element [vi, fi] in encoded1, the inner while loop processes exactly fi units. The key insight is that each unit in the expanded form of both arrays is processed exactly once:

• Each frequency unit from encoded1 is consumed exactly once through the fi -= f operation
• Each frequency unit from encoded2 is consumed exactly once through the encoded2[j][1] -= f operation
• The pointer j moves through encoded2 sequentially and never backtracks

Since the total number of operations is proportional to the number of segments in both encoded arrays (not the expanded frequencies), the time complexity is O(n + m).

Space Complexity: O(1) excluding the output array, or O(n + m) including the output array.

The algorithm uses only a constant amount of extra space:

• Variable j for indexing encoded2
• Variables vi, fi, f, and v for temporary storage during processing

The output array ans can contain at most n + m segments in the worst case (when no adjacent segments can be merged), giving a total space complexity of O(n + m) when including the output.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Modifying Input Arrays

The provided solution directly modifies encoded2 by decreasing its frequency values (encoded2[encoded2_index][1] -= min_frequency). This is problematic because:

• It mutates the input, which may be unexpected behavior
• If the function needs to be called multiple times with the same input, it will produce incorrect results
• It violates the principle of keeping functions pure when possible

Solution: Create local copies of the frequency values instead of modifying the input directly:

def findRLEArray(self, encoded1, encoded2):
    result = []
    i, j = 0, 0
    freq1, freq2 = 0, 0

    while i < len(encoded1) and j < len(encoded2):
        # Use local copies of frequencies
        if freq1 == 0:
            val1, freq1 = encoded1[i]
            i += 1
        if freq2 == 0:
            val2, freq2 = encoded2[j]
            j += 1

        # Process the minimum frequency
        min_freq = min(freq1, freq2)
        product = val1 * val2

        # Merge or append to result
        if result and result[-1][0] == product:
            result[-1][1] += min_freq
        else:
            result.append([product, min_freq])

        # Update local frequency counters
        freq1 -= min_freq
        freq2 -= min_freq

    return result

2. Forgetting to Merge Consecutive Segments

A common mistake is to append every product segment without checking if it can be merged with the previous one. This leads to unnecessarily long output arrays like [[3,1], [3,2], [8,3]] instead of [[3,3], [8,3]].

Solution: Always check if the last segment in the result has the same value before appending a new segment.

3. Index Out of Bounds

When using encoded2[encoded2_index], failing to ensure encoded2_index stays within bounds can cause crashes, especially if the arrays aren't actually the same expanded length as promised.

Solution: Add boundary checks or restructure the loop to naturally handle boundaries:

while i < len(encoded1) or j < len(encoded2):
    if i >= len(encoded1) or j >= len(encoded2):
        break  # Or handle error case
    # ... rest of logic

4. Not Handling Edge Cases

The solution might fail on edge cases like:

• Empty arrays
• Single-element encoded arrays [[5, 1]]
• Arrays with zero frequencies (though these shouldn't exist in valid RLE)

Solution: Add initial validation and handle edge cases explicitly:

if not encoded1 or not encoded2:
    return []