47. Median of Two Ranked Model-Output Streams

Problem

Two model variants — say, a standard and a "turbo" TTS variant — each produce a sorted list of quality scores for a batch of outputs during an offline A/B evaluation. To summarize the combined distribution, an evaluator wants the median of the merged, sorted set of both streams, without actually merging them, since both streams can be large and this runs for every comparison.

a and b are each already sorted ascending. Return the median of the combined sorted sequence of both. This must run in O(log(min(len(a), len(b)))) time — do not concatenate and sort.

Source: src/47_median_two_model_streams.py

def median_of_two_streams(a: list[float], b: list[float]) -> float:

>>> median_of_two_streams([1, 3], [2])
2.0

>>> median_of_two_streams([1, 2], [3, 4])
2.5

Step-by-Step Approach

1. Reframe "find the median of the merged array" as "find a partition point in each array such that everything to the left of both partitions is ≤ everything to the right of both" — if you can find that partition, the median falls right out of the four boundary elements without ever merging anything.
2. Always binary-search over the shorter array (swap if needed), which bounds the search space to O(log(min(m, n))) instead of O(log(m + n)) if you searched the longer one.
3. For a candidate cut index i in the shorter array, the corresponding cut j in the longer array is forced: the left half (across both arrays) must hold exactly (m + n + 1) // 2 elements total, so j = half - i.
4. Use -inf/+inf sentinels whenever a cut lands at an array's boundary (empty left or right side), so the boundary comparisons still work without special-casing.
5. Check whether the partition is balanced: the largest element on the left of a must be ≤ the smallest on the right of b, and vice versa. If not balanced, binary-search left or right based on which side is too large.
6. Once balanced, the median is derived directly: for odd total length it's the max of the two "left" boundary elements; for even length it's the average of the max-left and min-right boundary elements.

The key insight is that you never need the merged array itself — only its two (or one) middle elements, and those can be pinned down by binary-searching for a single balanced partition point rather than a full O(m + n) merge.

Reference solution

def median_of_two_streams(a: list[float], b: list[float]) -> float:
    # always binary-search the shorter array, so the search space is O(log(min(m,n)))
    if len(a) > len(b):
        a, b = b, a
    m, n = len(a), len(b)
    lo, hi = 0, m
    # left half (across both arrays combined) should hold this many elements
    half = (m + n + 1) // 2

    while lo <= hi:
        i = (lo + hi) // 2  # elements of `a` taken into the left half
        j = half - i  # elements of `b` taken into the left half

        # sentinels for out-of-range partitions so comparisons still work
        a_left = a[i - 1] if i > 0 else float("-inf")
        a_right = a[i] if i < m else float("inf")
        b_left = b[j - 1] if j > 0 else float("-inf")
        b_right = b[j] if j < n else float("inf")

        if a_left <= b_right and b_left <= a_right:
            # partition is correctly balanced: every left element <= every right element
            if (m + n) % 2 == 1:
                return float(max(a_left, b_left))
            return (max(a_left, b_left) + min(a_right, b_right)) / 2.0
        elif a_left > b_right:
            # `a` is taking too many elements into the left half, shrink it
            hi = i - 1
        else:
            # `a` is taking too few elements into the left half, grow it
            lo = i + 1

    raise ValueError("input arrays must be sorted")

Key Functions & Tricks

• Binary search on the shorter array — bounds the search to O(log(min(m, n))) instead of O(log(max(m, n))).
• j = half - i — the partition in the second array is fully determined by the partition in the first, so only one binary search is needed, not two.
• float("-inf") / float("inf") sentinels — let boundary partitions (cut at index 0 or at the array's length) reuse the same comparison logic with no special cases.
• Balance check (a_left <= b_right and b_left <= a_right) — the termination condition that confirms a valid median-defining partition has been found.
• Odd/even total-length branch — odd takes the max of the left boundaries; even averages the max-left and min-right boundaries.

How to Recognize This Pattern