Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1868.html

1868. Product of Two Run-Length Encoded Arrays

Level

Medium

Description

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] = [val_i, freq_i] describes the i-th segment of repeated numbers in nums where val_i is the value that is repeated freq_i 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 1s followed by five 2s”.

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] = [val_i, freq_i] describes the i-th segment of nums1, and each encoded2[j] = [val_j, freq_j] describes the j-th segment of nums2.

Return the product of encoded1 and encoded2.

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

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 <= val_i, freq_i <= 10^4 for each encoded1[i].
  • 1 <= val_j, freq_j <= 10^4 for each encoded2[j].
  • The full arrays that encoded1 and encoded2 represent are the same length.

Solution

Considering the constraints, it is impossible to expand both arrays and it is also impossible to store the uncompressed prodNums. Therefore, all the operations must be done on compessed arrays.

Use two pointers to point to indices of both encoded1 and encoded2. For the current values at index1 of encoded1 and index2 of encoded2, the current product is encoded1[index1][0] * encoded2[index2][0] and the current frequency is the minimum of encoded1[index1][1] and encoded2[index2][1]. If the current product is equal to the previous product, then update the product’s frequency. Otherwise, add the previous product and its frequency into the result list and update the product and the frequency. Finally, return the result list.

  • class Solution {
    public List<List<Integer>> findRLEArray(int[][] encoded1, int[][] encoded2) {
        List<List<Integer>> products = new ArrayList<List<Integer>>();
        int product = 0, count = 0;
        int length1 = encoded1.length, length2 = encoded2.length;
        int index1 = 0, index2 = 0;
        while (index1 < length1 && index2 < length2) {
            int val1 = encoded1[index1][0], val2 = encoded2[index2][0];
            int freq = Math.min(encoded1[index1][1], encoded2[index2][1]);
            encoded1[index1][1] -= freq;
            encoded2[index2][1] -= freq;
            int curProduct = val1 * val2;
            if (curProduct == product)
                count += freq;
            else {
                if (count > 0)
                    products.add(Arrays.asList(product, count));
                product = curProduct;
                count = freq;
            }
            if (encoded1[index1][1] == 0)
                index1++;
            if (encoded2[index2][1] == 0)
                index2++;
        }
        products.add(Arrays.asList(product, count));
        return products;
    }
}

  • class Solution {
public:
    vector<vector<int>> findRLEArray(vector<vector<int>>& encoded1, vector<vector<int>>& encoded2) {
        vector<vector<int>> ans;
        int j = 0;
        for (auto& e : encoded1) {
            int vi = e[0], fi = e[1];
            while (fi) {
                int f = min(fi, encoded2[j][1]);
                int v = vi * encoded2[j][0];
                if (!ans.empty() && ans.back()[0] == v) {
                    ans.back()[1] += f;
                } else {
                    ans.push_back({v, f});
                }
                fi -= f;
                encoded2[j][1] -= f;
                if (encoded2[j][1] == 0) {
                    ++j;
                }
            }
        }
        return ans;
    }
};

  • class Solution:
    def findRLEArray(
        self, encoded1: List[List[int]], encoded2: List[List[int]]
    ) -> List[List[int]]:
        ans = []
        j = 0
        for vi, fi in encoded1:
            while fi:
                f = min(fi, encoded2[j][1])
                v = vi * encoded2[j][0]
                if ans and ans[-1][0] == v:
                    ans[-1][1] += f
                else:
                    ans.append([v, f])
                fi -= f
                encoded2[j][1] -= f
                if encoded2[j][1] == 0:
                    j += 1
        return ans


  • func findRLEArray(encoded1 [][]int, encoded2 [][]int) (ans [][]int) {
	j := 0
	for _, e := range encoded1 {
		vi, fi := e[0], e[1]
		for fi > 0 {
			f := min(fi, encoded2[j][1])
			v := vi * encoded2[j][0]
			if len(ans) > 0 && ans[len(ans)-1][0] == v {
				ans[len(ans)-1][1] += f
			} else {
				ans = append(ans, []int{v, f})
			}
			fi -= f
			encoded2[j][1] -= f
			if encoded2[j][1] == 0 {
				j++
			}
		}
	}
	return
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

All Problems

All Solutions