Find median of merged RLE arrays

Problem

You are given two run-length encoded (RLE) arrays A and B. Each is sorted by value in non-decreasing order.

• Each element is a pair (value, frequency) meaning value appears frequency times in the underlying uncompressed array.
• Let UA be the uncompressed array represented by A , and UB similarly for B .
• Consider the fully merged multiset/array U = sort(UA ∪ UB) (i.e., as if you uncompressed both arrays and merged them into one sorted array).

Return the median of U.

Median Definition

Let N = len(U).

• If N is odd, the median is U[N//2] (0-indexed).
• If N is even, the median is (U[N//2 - 1] + U[N//2]) / 2 .

Constraints / Requirements

• frequency values may be very large, so you must not explicitly uncompress the arrays.
• A and B are individually sorted by value .

Example

A = [(1, 2), (5, 1)] represents [1, 1, 5]

B = [(2, 3)] represents [2, 2, 2]

Merged: [1, 1, 2, 2, 2, 5] → median is (2 + 2) / 2 = 2