Product of Two Run-Length Encoded Arrays

Problem

Run-length encoding is a compression algorithm that allows for an integer array nums with many segments of consecutive repeated numbers to be represented by a (generally smaller) 2D array encoded. Each encoded[i] = [vali, freqi] describes the ith segment of repeated numbers in nums where vali is the value that is repeated freqi times.

• For example, nums = [1,1,1,2,2,2,2,2] is represented by the run-length encoded array encoded = [[1,3],[2,5]]. Another way to read this is "three 1's followed by five 2's".

The product of two run-length encoded arrays encoded1 and encoded2 can be calculated using the following steps:

1. Expand both encoded1 and encoded2 into the full arrays nums1 and nums2 respectively.
2. Create a new array prodNums of length nums1.length and set prodNums[i] = nums1[i] * nums2[i].
3. Compress prodNums into a run-length encoded array and return it.

You are given two run-length encoded arrays encoded1 and encoded2 representing full arrays nums1 and nums2 respectively. Both nums1 and nums2 have the same length. Each encoded1[i] = [vali, freqi] describes the ith segment of nums1, and each encoded2[j] = [valj, freqj] describes the jth segment of nums2.

Return _theproduct of _encoded1 andencoded2.

Note: Compression should be done such that the run-length encoded array has the minimum possible length.

Examples

Example 1:

Input: encoded1 = [[1,3],[2,3]], encoded2 = [[6,3],[3,3]]
Output: [[6,6]]
Explanation: encoded1 expands to [1,1,1,2,2,2] and encoded2 expands to [6,6,6,3,3,3].
prodNums = [6,6,6,6,6,6], which is compressed into the run-length encoded array [[6,6]].

Example 2:

Input: encoded1 = [[1,3],[2,1],[3,2]], encoded2 = [[2,3],[3,3]]
Output: [[2,3],[6,1],[9,2]]
Explanation: encoded1 expands to [1,1,1,2,3,3] and encoded2 expands to [2,2,2,3,3,3].
prodNums = [2,2,2,6,9,9], which is compressed into the run-length encoded array [[2,3],[6,1],[9,2]].

Constraints:

• 1 <= encoded1.length, encoded2.length <= 10^5
• encoded1[i].length == 2
• encoded2[j].length == 2
• 1 <= vali, freqi <= 10^4 for each encoded1[i].
• 1 <= valj, freqj <= 10^4 for each encoded2[j].
• The full arrays that encoded1 and encoded2 represent are the same length.

Solution

Method 1 – Two-Pointer Merge and Compress

Intuition

We can process both run-length encoded arrays with two pointers, multiplying values and compressing the result on the fly. This avoids expanding the arrays and is efficient.

Approach

1. Use two pointers to iterate through encoded1 and encoded2.
2. At each step, multiply the current values and take the minimum frequency.
3. Add the product and frequency to the result, merging with the previous if the value is the same.
4. Decrement the frequencies and move pointers as needed.

Code

C++

class Solution {
public:
    vector<vector<int>> findRLEArray(vector<vector<int>>& encoded1, vector<vector<int>>& encoded2) {
        vector<vector<int>> res;
        int i = 0, j = 0;
        while (i < encoded1.size() && j < encoded2.size()) {
            int v1 = encoded1[i][0], f1 = encoded1[i][1];
            int v2 = encoded2[j][0], f2 = encoded2[j][1];
            int prod = v1 * v2, freq = min(f1, f2);
            if (!res.empty() && res.back()[0] == prod) res.back()[1] += freq;
            else res.push_back({prod, freq});
            encoded1[i][1] -= freq;
            encoded2[j][1] -= freq;
            if (encoded1[i][1] == 0) ++i;
            if (encoded2[j][1] == 0) ++j;
        }
        return res;
    }
};

Go

func findRLEArray(encoded1 [][]int, encoded2 [][]int) [][]int {
    res := [][]int{}
    i, j := 0, 0
    for i < len(encoded1) && j < len(encoded2) {
        v1, f1 := encoded1[i][0], encoded1[i][1]
        v2, f2 := encoded2[j][0], encoded2[j][1]
        prod, freq := v1*v2, min(f1, f2)
        if len(res) > 0 && res[len(res)-1][0] == prod {
            res[len(res)-1][1] += freq
        } else {
            res = append(res, []int{prod, freq})
        }
        encoded1[i][1] -= freq
        encoded2[j][1] -= freq
        if encoded1[i][1] == 0 { i++ }
        if encoded2[j][1] == 0 { j++ }
    }
    return res
}
func min(a, b int) int { if a < b { return a }; return b }

Java

import java.util.*;
class Solution {
    public List<List<Integer>> findRLEArray(int[][] encoded1, int[][] encoded2) {
        List<List<Integer>> res = new ArrayList<>();
        int i = 0, j = 0;
        while (i < encoded1.length && j < encoded2.length) {
            int v1 = encoded1[i][0], f1 = encoded1[i][1];
            int v2 = encoded2[j][0], f2 = encoded2[j][1];
            int prod = v1 * v2, freq = Math.min(f1, f2);
            if (!res.isEmpty() && res.get(res.size()-1).get(0) == prod)
                res.get(res.size()-1).set(1, res.get(res.size()-1).get(1) + freq);
            else
                res.add(Arrays.asList(prod, freq));
            encoded1[i][1] -= freq;
            encoded2[j][1] -= freq;
            if (encoded1[i][1] == 0) ++i;
            if (encoded2[j][1] == 0) ++j;
        }
        return res;
    }
}

Kotlin

class Solution {
    fun findRLEArray(encoded1: Array<IntArray>, encoded2: Array<IntArray>): List<List<Int>> {
        val res = mutableListOf<List<Int>>() 
        var i = 0; var j = 0
        while (i < encoded1.size && j < encoded2.size) {
            val (v1, f1) = encoded1[i]; val (v2, f2) = encoded2[j]
            val prod = v1 * v2; val freq = minOf(f1, f2)
            if (res.isNotEmpty() && res.last()[0] == prod)
                res[res.size-1] = listOf(prod, res.last()[1] + freq)
            else
                res.add(listOf(prod, freq))
            encoded1[i][1] -= freq
            encoded2[j][1] -= freq
            if (encoded1[i][1] == 0) i++
            if (encoded2[j][1] == 0) j++
        }
        return res
    }
}

Python

from typing import List
class Solution:
    def findRLEArray(self, encoded1: List[List[int]], encoded2: List[List[int]]) -> List[List[int]]:
        res = []
        i = j = 0
        while i < len(encoded1) and j < len(encoded2):
            v1, f1 = encoded1[i]
            v2, f2 = encoded2[j]
            prod, freq = v1 * v2, min(f1, f2)
            if res and res[-1][0] == prod:
                res[-1][1] += freq
            else:
                res.append([prod, freq])
            encoded1[i][1] -= freq
            encoded2[j][1] -= freq
            if encoded1[i][1] == 0:
                i += 1
            if encoded2[j][1] == 0:
                j += 1
        return res

Rust

impl Solution {
    pub fn find_rle_array(mut encoded1: Vec<Vec<i32>>, mut encoded2: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        let mut res = Vec::new();
        let (mut i, mut j) = (0, 0);
        while i < encoded1.len() && j < encoded2.len() {
            let (v1, f1) = (encoded1[i][0], encoded1[i][1]);
            let (v2, f2) = (encoded2[j][0], encoded2[j][1]);
            let prod = v1 * v2;
            let freq = f1.min(f2);
            if let Some(last) = res.last_mut() {
                if last[0] == prod {
                    last[1] += freq;
                } else {
                    res.push(vec![prod, freq]);
                }
            } else {
                res.push(vec![prod, freq]);
            }
            encoded1[i][1] -= freq;
            encoded2[j][1] -= freq;
            if encoded1[i][1] == 0 { i += 1; }
            if encoded2[j][1] == 0 { j += 1; }
        }
        res
    }
}

TypeScript

class Solution {
    findRLEArray(encoded1: number[][], encoded2: number[][]): number[][] {
        const res: number[][] = [];
        let i = 0, j = 0;
        while (i < encoded1.length && j < encoded2.length) {
            const [v1, f1] = encoded1[i], [v2, f2] = encoded2[j];
            const prod = v1 * v2, freq = Math.min(f1, f2);
            if (res.length && res[res.length-1][0] === prod) res[res.length-1][1] += freq;
            else res.push([prod, freq]);
            encoded1[i][1] -= freq;
            encoded2[j][1] -= freq;
            if (encoded1[i][1] === 0) i++;
            if (encoded2[j][1] === 0) j++;
        }
        return res;
    }
}

Complexity

• ⏰ Time complexity: O(N + M) where N and M are the lengths of the encoded arrays.
• 🧺 Space complexity: O(1) extra (output not counted).