Problem statement

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

Solution

The idea of this problem is to:

  1. Create events1 and events2 are distance from the beginning to starts of chunks: cumulative sums.
  2. Then we use two pointers approach: on each step we look which event is closer. If it is from E1, we move i to the right, if it is from E2, we move j to the right and if they are equal, move both. Also we keep right is current pointe we reached. Also we need to check if val of previous chunk is not the same as current, if they are equal, update last chunk.

Complexity

It is O(m + n) both for time and space. In fact, complexity can not be improved, because in the end we can have upto O(m + n) chunks.

Code

class Solution:
    def findRLEArray(self, E1, E2):
        events1 = list(accumulate(x for _, x in E1))
        events2 = list(accumulate(x for _, x in E2))
        E3 = []
        
        i, j, right = 0, 0, 0
        while i < len(events1) and j < len(events2):
            val = E1[i][0]*E2[j][0]
            right2 = min(events1[i], events2[j])
            freq = right2 - right
            right = right2
            i, j = i + (events1[i] <= events2[j]), j + (events1[i] >= events2[j])
            
            if E3 and E3[-1][0] == val:
                E3[-1][1] += freq
            else:
                E3 += [[val, freq]]
        
        return E3