Product of 2 run length encoded Arrays

XXX. Run-Length Encoded Multiplication

Array

Two Pointers

Math

Problem Statement:

You are given two run-length encoded arrays, encoded1 and encoded2, where each element is a pair of values [value, frequency]. Your task is to compute their element-wise product and return the result as a run-length encoded array. The result should be minimal, meaning consecutive elements with the same value should be merged.

Algorithm:

1. Use two pointers, e1 and e2, to traverse the two encoded arrays.
2. For each pair of elements from encoded1 and encoded2, calculate the common frequency and their product.
3. If the result array is not empty and the last element has the same product value, merge the frequencies.
4. Otherwise, add a new element to the result array with the product value and common frequency.
5. Decrement the frequencies of the current elements in encoded1 and encoded2 by the common frequency. If the frequency of an element becomes zero, move the corresponding pointer to the next element.
6. Repeat until both arrays are fully processed.

Complexity:

Time Complexity: O(m + n), where m and n are the lengths of encoded1 and encoded2 respectively.
Space Complexity: O(1) additional space for processing, and O(k) for the result, where k is the length of the output array.

Java Implementation:

public class Solution {
    public List<List<Integer>> findRLEArray(int[][] encoded1, int[][] encoded2) {
        // Result list to store the final RLE array
        List<List<Integer>> result = new ArrayList<>();
        int e1 = 0, e2 = 0; // Pointers for encoded1 and encoded2

        // Traverse both encoded arrays
        while (e1 < encoded1.length) {
            int[] first = encoded1[e1];
            int[] second = encoded2[e2];

            // Find the common frequency between the two current RLE elements
            int common = Math.min(first[1], second[1]);
            // Compute the product of the values
            int mul = first[0] * second[0];

            // Check if the last element in the result has the same value to merge frequencies
            if (!result.isEmpty() && result.get(result.size() - 1).get(0) == mul) {
                List prev = result.get(result.size() - 1);
                int prevFreq = prev.get(1);
                prev.set(1, prevFreq + common);
            } else {
                // Add a new entry to the result
                result.add(Arrays.asList(mul, common));
            }

            // Decrease the frequency in both encoded arrays
            first[1] -= common;
            second[1] -= common;

            // Move pointers if the frequency of an element becomes zero
            if (first[1] == 0) e1++;
            if (second[1] == 0) e2++;
        }

        return result;
    }
}
                

Python Implementation:

def find_rle_array(encoded1, encoded2):
    # Result list to store the final RLE array
    result = []
    e1, e2 = 0, 0 # Pointers for encoded1 and encoded2

    # Traverse both encoded arrays
    while e1 < len(encoded1):
        first = encoded1[e1]
        second = encoded2[e2]

        # Find the common frequency between the two current RLE elements
        common = min(first[1], second[1])
        # Compute the product of the values
        mul = first[0] * second[0]

        # Check if the last element in the result has the same value to merge frequencies
        if result and result[-1][0] == mul:
            result[-1][1] += common
        else:
            # Add a new entry to the result
            result.append([mul, common])

        # Decrease the frequency in both encoded arrays
        first[1] -= common
        second[1] -= common

        # Move pointers if the frequency of an element becomes zero
        if first[1] == 0:
            e1 += 1
        if second[1] == 0:
            e2 += 1

    return result
                

C++ Implementation:

#include 
using namespace std;

class Solution {
public:
    vector> findRLEArray(vector>& encoded1, vector>& encoded2) {
        // Result vector to store the final RLE array
        vector> result;
        int e1 = 0, e2 = 0; // Pointers for encoded1 and encoded2

        // Traverse both encoded arrays
        while (e1 < encoded1.size()) {
            auto& first = encoded1[e1];
            auto& second = encoded2[e2];

            // Find the common frequency between the two current RLE elements
            int common = min(first[1], second[1]);
            // Compute the product of the values
            int mul = first[0] * second[0];

            // Check if the last element in the result has the same value to merge frequencies
            if (!result.empty() && result.back()[0] == mul) {
                result.back()[1] += common;
            } else {
                // Add a new entry to the result
                result.push_back({mul, common});
            }

            // Decrease the frequency in both encoded arrays
            first[1] -= common;
            second[1] -= common;

            // Move pointers if the frequency of an element becomes zero
            if (first[1] == 0) e1++;
            if (second[1] == 0) e2++;
        }

        return result;
    }
};