Median of Two Sorted Arrays

This is the hard problem of the section and one of the best-known hard problems in interviews. A linear answer is easy. The O(log(m + n)) answer needs a new way to look at the median — not as "the middle value" but as "the place where the values split into two equal halves" — and then a binary search over where that split falls.

Take it slowly. Most of the lesson is the insight; the code is twenty lines once the insight is clear.

The problem

You are given two sorted lists of integers, a with m values and b with n values. Return the median of all m + n values together: the middle value if the total is odd, or the average of the two middle values if it is even. The running time must be O(log(m + n)).

• a = [1, 4, 7, 9], b = [2, 3, 8] → 4.0. Together: 1, 2, 3, 4, 7, 8, 9. Seven values; the 4th is 4.
• a = [1, 2], b = [3, 4] → 2.5. Together: 1, 2, 3, 4. The average of 2 and 3.

Constraints: 0 ≤ m, n ≤ 1000, m + n ≥ 1, values between -10⁶ and 10⁶.

Clarifying questions

• Can one list be empty? Yes, but not both.
• Can values repeat, within or across lists? Yes.
• Return type? A float, even when the median is a whole number.
• Are both sorted in increasing order? Yes.

Approach 1: the simple way

Join the two lists, sort, and read the middle.

1def median_by_sorting(a: list[int], b: list[int]) -> float:2    """Join, sort, and read the middle: O((m + n) log(m + n))."""3    merged = sorted(a + b)4    total = len(merged)5    if total % 2 == 1:6        return float(merged[total // 2])7    return (merged[total // 2 - 1] + merged[total // 2]) / 2

Time: O((m + n) log(m + n)). Space: O(m + n).

It ignores that both lists are already sorted, so it pays for a sort it does not need.

Approach 2: walk to the middle

Merge the two lists the way merge sort does — always take the smaller front value — but stop halfway, since the median is in the middle, and keep only the last two values seen:

1def median_by_walking(a: list[int], b: list[int]) -> float:2    """Merge-walk only to the middle, keeping the last two values: O(m + n), O(1) space."""3    total = len(a) + len(b)4    i = j = 05    previous = current = 06    for _ in range(total // 2 + 1):7        previous = current8        if j == len(b) or (i < len(a) and a[i] <= b[j]):9            current = a[i]10            i += 111        else:12            current = b[j]13            j += 114    if total % 2 == 1:15        return float(current)16    return (previous + current) / 2

Time: O(m + n). Space: O(1).

At 2,000 values, this runs instantly, so be honest in the interview: in practice this is a fine answer. But the problem demands O(log(m + n)), and that is the point of the question. The walk still looks at half of all values, one by one. To get a logarithm, you must throw away half of something at every step without looking at it.

The key insight

Stop thinking of the median as a value. Think of it as a cut.

If you lay all m + n values out in sorted order and cut them into a left half and a right half of equal size (the left gets the extra one when the total is odd), the median is decided by the values right at the cut: the biggest value on the left, and when the total is even, the smallest value on the right.

Now look at the cut from the point of view of the two lists. The left half takes some number of values from the front of a — call it i — and the rest from the front of b: j = half - i, where half = (m + n + 1) // 2. Once you choose i, j is fixed. So the whole problem is choosing one number, i, between 0 and m.

When is a choice of i right? The left half must hold only values that are at most every value in the right half. Inside each list that is automatic, because the lists are sorted. So only two cross-checks are needed:

• a[i - 1] <= b[j]: the last value a gives to the left is not bigger than the first value b keeps on the right.
• b[j - 1] <= a[i]: the same, the other way round.

And when a check fails, it tells you which way to move:

• If a[i - 1] > b[j], you took too many from a: a big value of a sits on the left. Make i smaller.
• If b[j - 1] > a[i], you took too few from a, so too many from b. Make i bigger.

That is a monotonic test on i. Smaller i values are "too few", larger ones "too many", and the right cut sits between them. So binary search over i. Search the shorter list, so that i ranges over at most min(m, n) + 1 values and j never goes below 0 or past n.

When i is 0 or m (or j is 0 or n), one side of the cut is empty. Treat a missing left value as minus infinity and a missing right value as plus infinity. Then the two checks work unchanged at the edges.

Approach 3: binary search the cut

1import math234def find_median_sorted_arrays(a: list[int], b: list[int]) -> float:5    """Median of two sorted arrays in O(log(min(m, n)))."""6    if len(a) > len(b):7        a, b = b, a                          # binary search the shorter array8    m, n = len(a), len(b)9    half = (m + n + 1) // 2                  # size of the left half (the extra one goes left)10    lo, hi = 0, m                            # i = how many values the left half takes from a11    while lo <= hi:12        i = (lo + hi) // 213        j = half - i                         # the rest of the left half comes from b14        a_left = a[i - 1] if i > 0 else -math.inf15        a_right = a[i] if i < m else math.inf16        b_left = b[j - 1] if j > 0 else -math.inf17        b_right = b[j] if j < n else math.inf18        if a_left > b_right:19            hi = i - 1                       # took too many from a20        elif b_left > a_right:21            lo = i + 1                       # took too few from a22        else:                                # every left value <= every right value23            if (m + n) % 2 == 1:24                return float(max(a_left, b_left))25            return (max(a_left, b_left) + min(a_right, b_right)) / 226    raise ValueError("inputs must be sorted")

The loop uses the inclusive template: i can be any of 0 … m, and a good cut always exists, so the loop returns from inside. The final raise only fires if the inputs were not sorted. At the good cut, the biggest left value is the larger of a_left and b_left, and the smallest right value is the smaller of a_right and b_right.

Dry run on a = [1, 4, 7, 9], b = [2, 3, 8]. The code swaps them so that a = [2, 3, 8] (the shorter) and b = [1, 4, 7, 9]. Then m = 3, n = 4, half = 4.

At step 2 the left half is [2, 3] from a and [1, 4] from b, and the right half is [8] and [7, 9]. The total, 7, is odd, so the median is the biggest left value: max(3, 4) = 4.0.

For [1, 2] and [3, 4]: half = 2. Step 1 tries i = 1, j = 1 and finds b_left = 3 bigger than a_right = 2, so lo = 2. Step 2 tries i = 2, j = 0: the left is [1, 2], the right is [3, 4], and the median is (2 + 3) / 2 = 2.5.

Time: O(log(min(m, n))), which is within the required O(log(m + n)). At 1,000 values in the shorter list, about 10 steps. Space: O(1). All three approaches were checked against each other on 500 random pairs, including empty lists and heavy duplicates.

Edge cases

• One list empty: after the swap, a is empty, m = 0, and the only choice is i = 0, j = half. The sentinels make both checks pass, and the median comes from b alone.
• All of a smaller than all of b: the good cut is i = m; a_right is plus infinity, so the second check passes.
• Duplicates: [1, 1] and [1, 1] gives 1.0. The checks use <=-style comparisons (they fail only on strictly bigger), so equal values never block a cut.
• Even total: the + 1 in half does nothing harmful; the average of the two middle values is computed from both sides of the cut.

Follow-ups

• "Find the k-th smallest value of the two lists." The same cut with half replaced by k, searching i in [max(0, k - n), min(k, m)]. Or the recursive version that discards k / 2 values from one list each step.
• "Values arrive one at a time; report the median after each." Different problem: keep two heaps, a max-heap for the lower half and a min-heap for the upper half. That is in the Heaps section.
• "Median of k sorted lists." Binary search on the value: for a candidate x, count values at most x across all lists with bisect_right, and find the first x whose count reaches the middle.