LC 1868 [M] Product of Two Run Length Encoded Arrays - ALawliet/algorithms GitHub Wiki

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

class Solution:
    def findRLEArray(self, encoded1: List[List[int]], encoded2: List[List[int]]) -> List[List[int]]:
        res = []

        e1_index = 0
        e2_index = 0

        while e1_index < len(encoded1) and e2_index < len(encoded2):
            # [0] = val, [1] = freq
            e1_val, e1_freq = encoded1[e1_index]
            e2_val, e2_freq = encoded2[e2_index]

            product_val = e1_val * e2_val
            product_freq = min(e1_freq, e2_freq) # choose the smaller freq

            # in-place subtract the freqs
            encoded1[e1_index][1] -= product_freq
            encoded2[e2_index][1] -= product_freq

            # in-place check and move the pointers if no freq mains
            if encoded1[e1_index][1] == 0: e1_index += 1
            if encoded2[e2_index][1] == 0: e2_index += 1

            # we can just check the last product cause it's in order
            if not res or res[-1][0] != product_val: # last val in answer does not match recent val used
                # new value and add it to the list
                res.append( [product_val, product_freq] )
            else:
                # old value and just count it
                res[-1][1] += product_freq

        return res