Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1868. Product of Two Run-Length Encoded Arrays - Leetcode Solution

Code Implementation

class Solution:
    def findRLEArray(self, encoded1, encoded2):
        res = []
        i, j = 0, 0
        n, m = len(encoded1), len(encoded2)
        while i < n and j < m:
            v1, c1 = encoded1[i]
            v2, c2 = encoded2[j]
            product = v1 * v2
            count = min(c1, c2)
            if res and res[-1][0] == product:
                res[-1][1] += count
            else:
                res.append([product, count])
            encoded1[i][1] -= count
            encoded2[j][1] -= count
            if encoded1[i][1] == 0:
                i += 1
            if encoded2[j][1] == 0:
                j += 1
        return res
      
class Solution {
public:
    vector<vector<int>> findRLEArray(vector<vector<int>>& encoded1, vector<vector<int>>& encoded2) {
        vector<vector<int>> res;
        int i = 0, j = 0, n = encoded1.size(), m = encoded2.size();
        while (i < n && j < m) {
            int v1 = encoded1[i][0], c1 = encoded1[i][1];
            int v2 = encoded2[j][0], c2 = encoded2[j][1];
            int product = v1 * v2;
            int count = min(c1, c2);
            if (!res.empty() && res.back()[0] == product) {
                res.back()[1] += count;
            } else {
                res.push_back({product, count});
            }
            encoded1[i][1] -= count;
            encoded2[j][1] -= count;
            if (encoded1[i][1] == 0) ++i;
            if (encoded2[j][1] == 0) ++j;
        }
        return res;
    }
};
      
class Solution {
    public List<List<Integer>> findRLEArray(int[][] encoded1, int[][] encoded2) {
        List<List<Integer>> res = new ArrayList<>();
        int i = 0, j = 0, n = encoded1.length, m = encoded2.length;
        while (i < n && j < m) {
            int v1 = encoded1[i][0], c1 = encoded1[i][1];
            int v2 = encoded2[j][0], c2 = encoded2[j][1];
            int product = v1 * v2;
            int count = Math.min(c1, c2);
            if (!res.isEmpty() && res.get(res.size() - 1).get(0) == product) {
                res.get(res.size() - 1).set(1, res.get(res.size() - 1).get(1) + count);
            } else {
                res.add(Arrays.asList(product, count));
            }
            encoded1[i][1] -= count;
            encoded2[j][1] -= count;
            if (encoded1[i][1] == 0) i++;
            if (encoded2[j][1] == 0) j++;
        }
        return res;
    }
}
      
var findRLEArray = function(encoded1, encoded2) {
    const res = [];
    let i = 0, j = 0;
    while (i < encoded1.length && j < encoded2.length) {
        let [v1, c1] = encoded1[i];
        let [v2, c2] = encoded2[j];
        let product = v1 * v2;
        let count = Math.min(c1, c2);
        if (res.length > 0 && res[res.length - 1][0] === product) {
            res[res.length - 1][1] += count;
        } else {
            res.push([product, count]);
        }
        encoded1[i][1] -= count;
        encoded2[j][1] -= count;
        if (encoded1[i][1] === 0) i++;
        if (encoded2[j][1] === 0) j++;
    }
    return res;
};

Problem Description

Given two arrays, encoded1 and encoded2, each representing a run-length encoding (RLE) of an underlying array, return the run-length encoding of the element-wise product of the original arrays. Each encoded array consists of pairs [value, frequency], meaning the value repeats frequency times in the original array. The two original arrays are of the same length. The output should also be in run-length encoded format, merging adjacent runs if their product values are equal.

Thought Process

At first glance, you might think about expanding both RLE arrays to their full forms, multiplying element-by-element, and then re-encoding the result. However, this would be inefficient, especially for large inputs with big frequencies. Instead, since both encoded arrays are already compressed, we can process them in-place, matching up their runs as we go, and emitting the product in RLE form directly. The key is to walk through both arrays simultaneously, always multiplying the current values for as many elements as their minimum remaining frequencies allow, and then moving forward in the array whose current run ends first.

Solution Approach

  • Initialize two pointers, one for each encoded array, both starting at the beginning.
  • At each step, look at the current run in each array: [value1, freq1] and [value2, freq2].
  • The number of elements you can process in this step is min(freq1, freq2).
  • Multiply value1 and value2 to get the product for this run, and emit [product, count] to the result.
  • If the last emitted run in the result has the same product value, merge them by summing the frequencies instead of creating a new run.
  • Subtract count from both freq1 and freq2. If either frequency reaches zero, advance that pointer to the next run in its array.
  • Repeat until both arrays are fully processed.
This approach efficiently processes the arrays without ever expanding them, and directly produces the RLE output.

Example Walkthrough

Consider encoded1 = [[1,3],[2,3]] and encoded2 = [[6,3],[3,3]].
  • First, [1,3] and [6,3] line up. The minimum frequency is 3, so we multiply 1*6=6 for 3 times. Output: [[6,3]].
  • Move to next runs: [2,3] and [3,3]. Again, min freq is 3, so 2*3=6 for 3 times. Since the previous output run was also 6, we merge: [[6,6]].
  • Both arrays are done. Final output: [[6,6]].
This demonstrates how the merging and pointer movement works in practice.

Time and Space Complexity

  • Brute-force: Expanding both arrays to their full length would be O(N), where N is the total number of elements, and re-encoding would also be O(N) time and space.
  • Optimized solution: We process each run exactly once, so the time complexity is O(L1 + L2), where L1 and L2 are the lengths of the encoded arrays. Space complexity is O(L1 + L2) in the worst case for the output, though usually less because of merging.
This is much more efficient than expanding the arrays.

Summary

By leveraging the compressed structure of run-length encoding, we efficiently compute the element-wise product by processing runs in-place. This avoids unnecessary expansion and recompression, keeps code simple, and ensures optimal time and space usage. The solution is elegant because it works directly with the compressed format and merges adjacent runs automatically.