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 rather than “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.