Median of Two Sorted Arrays — InterviewPrepKit

Problem

You are given two sorted integer arrays, nums1 (length m) and nums2 (length n). Return the median of all m + n numbers taken together, as a float.

The median of a sorted sequence is its middle element when the length is odd, and the average of the two middle elements when the length is even. The required time complexity is O(log(m + n)) — merging the arrays is not the intended answer.

Examples

nums1 = [1,3], nums2 = [2] → 2.0 Merged: [1,2,3]; the middle element is 2.
nums1 = [1,2], nums2 = [3,4] → 2.5 Merged: [1,2,3,4]; the two middle elements 2 and 3 average to 2.5.
nums1 = [], nums2 = [5] → 5.0 One array may be empty; the median comes entirely from the other.

Constraints

0 <= m, n <= 1000 and 1 <= m + n <= 2000
-10^6 <= values <= 10^6
Required time: O(log(m + n)) — this is what makes the problem Hard.

Think about it first

Hint 1

The median splits the combined multiset into a left part and a right part of known sizes, where everything on the left is ≤ everything on the right. You don't need the merged array — only that split.

Hint 2

Any left part of total size `(m + n + 1) // 2` is formed by taking some prefix of `nums1` (say `i` elements) and a prefix of `nums2` (then forced to be `(m + n + 1) // 2 - i` elements). Only one value of `i` makes the split valid. What condition makes a split valid, and can you check it in O(1)?

Hint 3

Binary search on `i` over the shorter array. The split is valid when `nums1[i-1] <= nums2[j]` and `nums2[j-1] <= nums1[i]` (treat out-of-range as ±infinity). If `nums1[i-1] > nums2[j]`, the cut in `nums1` is too far right — shrink; otherwise grow. The median then comes from the max of the left parts (and, for even totals, the min of the right parts).

TL;DR

Binary search the partition point in the shorter array — O(log min(m, n)) time, O(1) space.

Approach 1 — Brute force

Concatenate, sort, take the middle.

from typing import List


def findMedianSortedArrays(nums1: List[int], nums2: List[int]) -> float:
    merged = sorted(nums1 + nums2)
    total = len(merged)
    mid = total // 2
    if total % 2 == 1:
        return float(merged[mid])
    return (merged[mid - 1] + merged[mid]) / 2

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

This ignores that the inputs are already sorted. At m + n ≤ 2000 it runs quickly, but the problem requires O(log(m+n)), so it serves only as a baseline.

Approach 2 — Merge with two pointers (no full sort)

Because both inputs are sorted, the merge step of merge sort (repeatedly taking the smaller of the two heads) produces the combined order in linear time. You only need to advance to the middle, not build the whole merged array.

from typing import List


def findMedianSortedArrays(nums1: List[int], nums2: List[int]) -> float:
    m, n = len(nums1), len(nums2)
    total = m + n
    i = j = 0
    prev = curr = 0
    for _ in range(total // 2 + 1):
        prev = curr
        if i < m and (j >= n or nums1[i] <= nums2[j]):
            curr = nums1[i]
            i += 1
        else:
            curr = nums2[j]
            j += 1
    if total % 2 == 1:
        return float(curr)
    return (prev + curr) / 2

Walkthrough on nums1 = [1,3], nums2 = [2] (total 3, loop runs 3 // 2 + 1 = 2 times):

Compare 1 vs 2 → take 1 (curr = 1, i = 1).
Compare 3 vs 2 → take 2 (prev = 1, curr = 2, j = 1).

Odd total → return 2.0. Correct.

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

Linear time, but still not O(log(m+n)).

Approach 3 — Binary search the partition

The median corresponds to a split of the combined multiset into a left half of size (m+n+1) // 2 and a right half, with max(left) <= min(right). Every such split takes i elements from the front of nums1 and j = half - i from the front of nums2, so the problem reduces to finding the one valid i. Validity is checkable in O(1): the split is valid iff nums1[i-1] <= nums2[j] and nums2[j-1] <= nums1[i] (out-of-range values count as ±infinity). The check is monotonic in i: if the nums1 cut is too far right (nums1[i-1] > nums2[j]), every larger i is too, so binary search over i in the shorter array works.

This is binary search in its “find the boundary of a monotonic predicate” form instead of “find a value”. Each iteration picks a cut and moves one boundary:

flowchart TD
    A["i = (lo + hi) / 2, j = half - i"] --> B{"left1 <= right2<br/>and left2 <= right1?"}
    B -- yes --> C["Valid split: return median"]
    B -- no --> D{"left1 > right2?"}
    D -- yes --> E["Cut too far right: hi = i - 1"]
    D -- no --> F["Cut too far left: lo = i + 1"]
    E --> A
    F --> A

from typing import List


def findMedianSortedArrays(nums1: List[int], nums2: List[int]) -> float:
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1          # binary search the shorter one
    m, n = len(nums1), len(nums2)
    half = (m + n + 1) // 2
    INF = float("inf")

    lo, hi = 0, m
    while lo <= hi:
        i = (lo + hi) // 2                   # take i from nums1 ...
        j = half - i                         # ... and j from nums2
        left1 = nums1[i - 1] if i > 0 else -INF
        right1 = nums1[i] if i < m else INF
        left2 = nums2[j - 1] if j > 0 else -INF
        right2 = nums2[j] if j < n else INF

        if left1 <= right2 and left2 <= right1:      # valid split
            if (m + n) % 2 == 1:
                return float(max(left1, left2))
            return (max(left1, left2) + min(right1, right2)) / 2
        if left1 > right2:                           # nums1 cut too far right
            hi = i - 1
        else:                                        # nums1 cut too far left
            lo = i + 1
    raise ValueError("inputs must be sorted")

Walkthrough on nums1 = [1,2], nums2 = [3,4] (m = n = 2, half = 2):

lo	hi	i	j	left1/right1	left2/right2	verdict
0	2	1	1	1 / 2	3 / 4	`left2 = 3 > right1 = 2` → cut too far left, lo = 2
2	2	2	0	2 / +inf	−inf / 3	valid: `2 <= 3` and `−inf <= +inf`

Even total → (max(2, −inf) + min(+inf, 3)) / 2 = (2 + 3) / 2 = 2.5. Correct.

The empty-array example nums1 = [], nums2 = [5] also falls out: after the swap m = 0, the only candidate is i = 0, j = 1, sentinels make it valid, and max(−inf, 5) = 5.0.

Time. O(log min(m, n)) — even better than the required O(log(m+n)).
Space. O(1).

Common pitfalls

Binary searching the longer array: then j = half - i can go negative (or exceed n), indexing out of bounds. Always swap so nums1 is the shorter.
Using (m + n) // 2 instead of (m + n + 1) // 2 for the left half — the +1 puts the odd-length median into the left half, so the odd case is simply max(left1, left2).
Forgetting the ±infinity sentinels for cuts at the very ends (i = 0, i = m, j = 0, j = n) — these are exactly the empty-array and disjoint-range cases.
Returning an int — the answer must be a float, and the even case must use true division / 2, not // 2.

Pattern takeaway

The advanced form of binary search doesn’t search for an element — it searches over configurations (here, partition positions) using a monotonic validity test. When a problem asks for a statistic of merged sorted data in log time, reframe it as “find the cut satisfying a ≤-condition”, verify the condition in O(1) with boundary sentinels, and binary search the smaller degree of freedom.