1868. Product of Two Run‐Length Encoded Arrays - cocoder39/coco39_LC GitHub Wiki

1868. Product of Two Run-Length Encoded Arrays

initial solution advances one product each iteration. time complexity is O(X) where X is the total length of uncompressed array

class Solution:
    def findRLEArray(self, encoded1: List[List[int]], encoded2: List[List[int]]) -> List[List[int]]:
        idx1, idx2 = 0, 0
        proceed1, proceed2, proceed = 0, 0, 0
        res = []
        while idx1 < len(encoded1) and idx2 < len(encoded2):
            val = encoded1[idx1][0] * encoded2[idx2][0]
            proceed += 1
            if not res or res[-1][0] != val:
                res.append([val, 1])
            else:
                res[-1] = [val, res[-1][1] + 1]

            if proceed1 + encoded1[idx1][1] == proceed:
                proceed1 += encoded1[idx1][1]
                idx1 += 1
            if proceed2 + encoded2[idx2][1] == proceed:
                proceed2 += encoded2[idx2][1]
                idx2 += 1
            #print(res, idx1, proceed1, idx2, proceed2)
        return res

revised solution generates min(encoded1[idx1][1], encoded2[idx2][1]) products, so at least one index would move forward. time complexity is O(len(encoded1) + len(encoded2))

class Solution:
    def findRLEArray(self, encoded1: List[List[int]], encoded2: List[List[int]]) -> List[List[int]]:
        idx1, idx2 = 0, 0
        res = []
        while idx1 < len(encoded1) and idx2 < len(encoded2):
            val = encoded1[idx1][0] * encoded2[idx2][0]
            dup = min(encoded1[idx1][1], encoded2[idx2][1])
            encoded1[idx1] = [encoded1[idx1][0], encoded1[idx1][1]-dup]
            encoded2[idx2] = [encoded2[idx2][0], encoded2[idx2][1]-dup]
            
            if not res or res[-1][0] != val:
                res.append([val, dup])
            else:
                res[-1] = [val, res[-1][1] + dup]

            
            if encoded1[idx1][1] == 0:
                idx1 += 1
            if encoded2[idx2][1] == 0:
                idx2 += 1
            #print(res, idx1, proceed1, idx2, proceed2)
        return res