Multiply Compressed Sequences

Medium

Long sequences full of repeats are handy to store compressed: a pair [value, count] means the number value appears count times in a row. For example, [[7, 2], [4, 3]] stands for [7, 7, 4, 4, 4]. You are given two compressed sequences, first and second. Once expanded, they have the same length. Multiply them element by element (the i-th by the i-th) and return the result, compressed as well. The compression must be as short as possible: two neighbouring pieces with the same value are merged into one. Avoid expanding the sequences in full, since they can get very long.

Example 1

first=[[2, 4]], second=[[3, 1], [5, 3]] → [[6, 1], [10, 3]]

Expanded: [2, 2, 2, 2] and [3, 5, 5, 5]. The products are [6, 10, 10, 10]: one 6 followed by three 10s.

Example 2

first=[[1, 2], [3, 2]], second=[[6, 2], [2, 2]] → [[6, 4]]

The result is [6, 6, 6, 6]. Equal neighbouring pieces must be merged into one: [[6, 4]], not [[6, 2], [6, 2]].

Constraints

1 ≤ len(first), len(second) ≤ 10⁵
Each element is a pair [value, count] with 1 ≤ value, count ≤ 10⁴
The expanded sequences have the same length

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Two Pointers

Similar problems

Two Boards Holding Water Medium Zero-Sum Triples Medium Triple Sum Nearest the Target Medium Four Numbers to a Target Medium Next Arrangement in Order Medium

Input

first=[[2, 4]], second=[[3, 1], [5, 3]]

Expected

[[6, 1], [10, 3]]

Run checks the first 3 tests in your browser. Submit checks all 100 tests on the server, hidden ones included.