Median of Two Sorted Arrays — InterviewPrepKit

Solving tips

Recognize this as partition-finding, not element-finding: the median is just a valid split of the combined data into a left half of size (m+n+1)//2 and a right half where max(left) <= min(right).
Binary search the cut position i over the SHORTER array (swap first); j = half - i is then forced, so you only have one degree of freedom. A split is valid iff nums1[i-1] <= nums2[j] and nums2[j-1] <= nums1[i].
Use +/-infinity sentinels for out-of-range cuts (i=0, i=m, j=0, j=n) so empty-array and edge cases fall out for free.
Target O(log(min(m,n))) time, O(1) space; use (m+n+1)//2 (the +1) so the odd-length median lands in the left half and the odd case is simply max(left1,left2).

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


class Solution:
    def findMedianSortedArrays(self, 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).

It even ignores that the inputs are sorted. At m + n ≤ 2000 it runs instantly, but the problem demands O(log(m+n)) — the constraint is about the technique, not the clock.

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

The insight: the inputs are already sorted, so the classical merge step of merge sort — repeatedly take the smaller head of the two arrays — produces the combined order in linear time. Better yet, you only need to advance to the middle, not build the whole merged array.

from typing import List


class Solution:
    def findMedianSortedArrays(self, 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, simple, and the right warm-up — but still not O(log(m+n)).

Approach 3 — Binary search the partition

The insight: the median is just 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 whole problem collapses 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). And 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.

Binary search here is used in its “find the boundary of a monotonic predicate” form rather than “find a value”.

from typing import List


class Solution:
    def findMedianSortedArrays(self, 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.