1868. Product of Two Run-Length Encoded Arrays (Array, Two Pointers)

링크 - https://leetcode.com/problems/product-of-two-run-length-encoded-arrays/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

각 encoded list에 있는 frequency 값들을 빼주면서 계산하고 idx를 증가시키면 된다.

Code

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

        ans = []
        while idx1 < len(encoded1) and idx2 < len(encoded2):
            val1, freq1 = encoded1[idx1]
            val2, freq2 = encoded2[idx2]

            product_val = val1 * val2
            product_freq = min(freq1, freq2)

            encoded1[idx1][1] -= product_freq
            encoded2[idx2][1] -= product_freq

            if encoded1[idx1][1] == 0:
                idx1 += 1
            if encoded2[idx2][1] == 0:
                idx2 += 1

            if ans and ans[-1][0] == product_val:
                ans[-1][1] += product_freq
            else:
                ans.append([product_val, product_freq])

        return ans

Complexity

Time Complexity: O(n)

Space Complexity: O(1)