Problem statement

https://binarysearch.com/problems/Compressed-Vector-Product/

Solution

Similar to Leetcode 1868 Product of Two Run-Length Encoded Arrays, but simpler, because we need to return product only.

Complexity

It is O(n + m) for time and O(1) for space.

Code

class Solution:
    def solve(self, a, b):
        i, j, ans, m, n = 0, 0, 0, len(a), len(b)
        while i < m and j < n:
            step = min(a[i], b[j])
            ans += step * a[i + 1] * b[j + 1]
            a[i] -= step
            b[j] -= step
            if a[i] == 0: i += 2
            if b[j] == 0: j += 2
        return ans