Product Of Two Run Length Encoded Arrays - Leetcode Solution

Problem Statement:

Given two run-length encoded arrays, return their product.

The two arrays are given as follows:

The first array is represented by an array of positive integers where each even index indicates the number of consecutive occurrences of the positive integer followed by the odd index element. For example, [1,3,2,1] represents the sequence [1,1,1,2].

The second array is represented by an array of positive integers where each even index indicates the number of consecutive occurrences of the positive integer followed by the odd index element. For example, [2,1,3,2] represents the sequence [2,1,1,1,1,3].

Return the product of these two run-length encoded arrays in the form of a run-length encoded array.

Solution:

To solve this problem, we first need to decode the two input arrays. After decoding them, we can multiply them element-wise and then re-encode the product array. Here are the steps we need to follow:

1. Create a function to decode a run-length encoded array.

   def decode(arr): decoded_arr = [] for i in range(0, len(arr), 2): count = arr[i] num = arr[i+1] for j in range(count): decoded_arr.append(num) return decoded_arr

2. Decode the two input arrays.

   arr1 = [1,3,2,1] arr2 = [2,1,3,2]

   decoded_arr1 = decode(arr1) decoded_arr2 = decode(arr2)

   print(decoded_arr1) # Output: [1, 1, 1, 2] print(decoded_arr2) # Output: [2, 1, 1, 1, 1, 3]

3. Multiply the decoded arrays element-wise.

   product_arr = [] i = 0 j = 0

   while i < len(decoded_arr1) and j < len(decoded_arr2): product_arr.append(decoded_arr1[i] * decoded_arr2[j]) if i+1 < len(decoded_arr1) and decoded_arr1[i] == decoded_arr1[i+1]: i += 2 else: i += 1 if j+1 < len(decoded_arr2) and decoded_arr2[j] == decoded_arr2[j+1]: j += 2 else: j += 1

   print(product_arr) # Output: [2, 1, 1, 2, 3]

4. Create a function to encode a decoded array.

   def encode(arr): encoded_arr = [] count = 1 for i in range(1, len(arr)): if arr[i] == arr[i-1]: count += 1 else: encoded_arr.append(count) encoded_arr.append(arr[i-1]) count = 1 encoded_arr.append(count) encoded_arr.append(arr[-1]) return encoded_arr

5. Encode the product array.

   encoded_arr = encode(product_arr)

   print(encoded_arr) # Output: [1, 2, 1, 1, 1, 2, 1, 3]

6. The final encoded array [1, 2, 1, 1, 1, 2, 1, 3] represents the product of the run-length encoded arrays [1,3,2,1] and [2,1,3,2].

1