Leetcode 2019 Solution

This article provides solution to leetcode question 2019 (product-of-two-run-length-encoded-arrays)
Categories:
Tags:
Access this page by simply typing in "lcs 2019" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/product-of-two-run-length-encoded-arrays

Solution

class Solution:
    def findRLEArray(self, encoded1: List[List[int]], encoded2: List[List[int]]) -> List[List[int]]:
        def transform(encoded):
            data = []
            i = 0
            for val, freq in encoded:
                i += freq
                data.append((val, i))
            return data



        data1 = transform(encoded1)
        data2 = transform(encoded2)



        i, j, k = 0, 0, 0
        ans = []
        while i < len(data1) and j < len(data2):
            if data1[i][1] == data2[j][1]:
                ans.append((data1[i][0] * data2[j][0], (data1[i][1] - k)))
                k = data1[i][1]
                i += 1
                j += 1
            elif data1[i][1] > data2[j][1]:
                ans.append((data1[i][0] * data2[j][0], (data2[j][1] - k)))
                k = data2[j][1]
                j += 1
            elif data1[i][1] < data2[j][1]:
                ans.append((data1[i][0] * data2[j][0], (data1[i][1] - k)))
                k = data1[i][1]
                i += 1



            if len(ans) >= 2 and ans[-1][0] == ans[-2][0]:
                val1, freq1 = ans.pop()
                val2, freq2 = ans.pop()
                ans.append((val1, freq1 + freq2))



        return ans