Median of Two Sorted Arrays (LC 4)

Problem Statement

Given two sorted arrays nums1 of size m and nums2 of size n, return the median of the combined sorted array.

The overall run time complexity should be O(log(m + n)).

Example 1:

Input:  nums1 = [1, 3], nums2 = [2]
Output: 2.0
Merged: [1, 2, 3] → median 2.

Example 2:

Input:  nums1 = [1, 2], nums2 = [3, 4]
Output: 2.5
Merged: [1, 2, 3, 4] → median (2+3)/2 = 2.5.

Constraints:

• 0 <= m, n <= 1000
• 1 <= m + n <= 2000
• -10^6 <= nums[i] <= 10^6

Difficulty: Hard

---

Pattern Recognition

• Input structure: two sorted arrays.
• What are we finding? the median — the value(s) at the middle of the merged order.
• Pattern: binary search on a partition point.
• Why: you do not need to merge; you need to find where to split nums1 such that the combined left half has exactly (m+n+1)/2 elements and every left-element ≤ every right-element. That's two constraints, one degree of freedom, which is exactly what binary search handles.

Google loves this problem because it turns a "merge then pick middle" intuition into a rigorous binary-search-on-answer. Nailing the invariants matters more than the code.

---

Approach

Brute Force

Merge the arrays (O(m + n)) and pick the middle element(s). Simple, correct, but not O(log).

Optimal — Binary Search on Partition

Key Insight: Pick i elements from nums1 and j = (m+n+1)/2 - i elements from nums2 to form the left half. Adjust i until nums1[i-1] <= nums2[j] AND nums2[j-1] <= nums1[i].

Conventions for edge behavior:

• nums1[-1] = nums2[-1] = -∞ (no element from that side on the left)
• nums1[m] = nums2[n] = +∞ (no element from that side on the right)

Always binary-search the shorter array to guarantee O(log min(m, n)) and simpler bounds.

if m > n: swap nums1 and nums2
lo = 0, hi = m
total_left = (m + n + 1) / 2
while lo <= hi:
    i = (lo + hi) / 2
    j = total_left - i
    L1 = (i == 0) ? -INF : nums1[i-1]
    R1 = (i == m) ? +INF : nums1[i]
    L2 = (j == 0) ? -INF : nums2[j-1]
    R2 = (j == n) ? +INF : nums2[j]

    if L1 <= R2 and L2 <= R1:
        if (m + n) is odd: return max(L1, L2)
        else: return (max(L1, L2) + min(R1, R2)) / 2
    else if L1 > R2: hi = i - 1
    else: lo = i + 1

Time: O(log min(m, n)). Space: O(1).

---

Walkthrough

nums1 = [1, 3, 8, 9, 15], nums2 = [7, 11, 18, 19, 21, 25], m=5, n=6, total_left = 6.

lo	hi	i	j	L1	R1	L2	R2	Check	Decision
0	5	2	4	3	8	19	21	L2(19) > R1(8)	move i right, lo = 3
3	5	4	2	9	15	11	18	L1(9) ≤ R2(18), L2(11) ≤ R1(15) ✓	found!

m + n = 11 (odd). Answer = max(L1, L2) = max(9, 11) = 11.

Sanity: merged = [1, 3, 7, 8, 9, 11, 15, 18, 19, 21, 25]. 11 elements, middle is index 5 = 11. ✓

---

Implementation

TypeScript

function findMedianSortedArrays(nums1: number[], nums2: number[]): number {
    // Always binary search the shorter array
    if (nums1.length > nums2.length) [nums1, nums2] = [nums2, nums1];

    const m = nums1.length, n = nums2.length;
    const totalLeft = Math.floor((m + n + 1) / 2);
    let lo = 0, hi = m;

    while (lo <= hi) {
        const i = (lo + hi) >> 1;
        const j = totalLeft - i;

        const L1 = i === 0 ? -Infinity : nums1[i - 1];
        const R1 = i === m ? Infinity : nums1[i];
        const L2 = j === 0 ? -Infinity : nums2[j - 1];
        const R2 = j === n ? Infinity : nums2[j];

        if (L1 <= R2 && L2 <= R1) {
            if ((m + n) % 2 === 1) return Math.max(L1, L2);
            return (Math.max(L1, L2) + Math.min(R1, R2)) / 2;
        } else if (L1 > R2) {
            hi = i - 1;       // too many from nums1
        } else {
            lo = i + 1;       // too few from nums1
        }
    }
    return 0.0; // unreachable for valid input
}

C++

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    if (nums1.size() > nums2.size()) swap(nums1, nums2);
    int m = nums1.size(), n = nums2.size();
    int totalLeft = (m + n + 1) / 2;
    int lo = 0, hi = m;

    while (lo <= hi) {
        int i = (lo + hi) / 2;
        int j = totalLeft - i;

        int L1 = (i == 0) ? INT_MIN : nums1[i - 1];
        int R1 = (i == m) ? INT_MAX : nums1[i];
        int L2 = (j == 0) ? INT_MIN : nums2[j - 1];
        int R2 = (j == n) ? INT_MAX : nums2[j];

        if (L1 <= R2 && L2 <= R1) {
            if ((m + n) % 2 == 1) return max(L1, L2);
            return (max(L1, L2) + min(R1, R2)) / 2.0;
        } else if (L1 > R2) {
            hi = i - 1;
        } else {
            lo = i + 1;
        }
    }
    return 0.0;
}

Watch out:

1. Binary searching the longer array makes the bound checks messier and can overflow j. Always put the shorter array first.
2. totalLeft = (m + n + 1) / 2 — the +1 makes the formula work for both even and odd total lengths.
3. Forgetting the ±∞ sentinels for i == 0, i == m, j == 0, j == n is the #1 bug source.

---

Complexity Analysis

	Time	Space
Merge	O(m + n)	O(m + n)
Two-pointer (no merge)	O(m + n)	O(1)
Binary Search on Partition	O(log min(m, n))	O(1)

Bottleneck: you reduce from O(m + n) to O(log min(m, n)) by exploiting the sortedness. Without sortedness, O(m + n) is a theoretical lower bound.

---

Edge Cases

1. One array empty — answer is median of the other. Your sentinel logic handles this.
2. All elements of nums1 < all of nums2 — i converges to m (or 0); sentinels prevent indexing errors.
3. Duplicates across arrays — <= in checks handles this correctly.
4. Even vs odd total length — the +1 in totalLeft and the %2 branch combine cleanly.
5. Single element inputs — m = 0, n = 1 → totalLeft = 1, i = 0, j = 1. Answer = nums2[0].
6. Integer overflow on sum in C++ — use double division or cast carefully in the average.

---

Related Problems

• LC 378 — Kth Smallest Element in a Sorted Matrix — Binary search on the value range, another "binary search on answer" pattern.
• LC 786 — K-th Smallest Prime Fraction — Binary search on fraction value.
• LC 719 — Find K-th Smallest Pair Distance — Same flavor applied to pair distances.
• LC 295 — Find Median from Data Stream — Streaming version; two heaps instead of binary search.

---

What Is Expected at Each Level

Junior: Deliver the O(m + n) merge solution and state complexity. Maybe discuss two-pointer no-merge at O(m + n), O(1) space.

Mid-level: Explain the partition invariant and attempt the binary-search-on-partition approach, possibly with small bugs around sentinels.

Senior (L4 target): Implement the binary-search version cleanly, justify the +1 in totalLeft, handle all sentinel cases, and generalize to "k-th smallest of two sorted arrays" for free. Discuss that this generalizes to "binary search on answer" — a pattern Google interviewers will chain into follow-up questions.