Median of Two Sorted Arrays — Binary Search Partition Interview Guide

Problem Statement#

Given two sorted arrays nums1 and nums2 of sizes m and n, return the median of the merged sorted array. Solution must run in O(log(m + n)).

Constraints:

• nums1.length == m, nums2.length == n
• 0 <= m, n <= 1000 and 1 <= m + n <= 2000
• -10^6 <= nums1[i], nums2[i] <= 10^6

Input:  nums1 = [1, 3], nums2 = [2]
Output: 2.0

Input:  nums1 = [1, 2], nums2 = [3, 4]
Output: 2.5

Why This Problem Matters#

LeetCode 4 is arguably the most asked binary search interview problem at Google, Amazon, and Meta. It looks innocent — find a median — but requires you to break the obvious linear merge and search a structural property instead. Interviewers use it to separate candidates who can recite binary search from those who can design with it.

Beyond the FAANG O(log n) prestige, this problem teaches the most generalizable binary search idea on the platform: searching for the position of a partition rather than a value. That mental model recurs in problems like Split Array Largest Sum, Kth Smallest in a Matrix, and many real systems engineering problems involving balanced splits.

If you can derive and explain the partition invariant under interview pressure, you signal mastery of the entire search-on-answer family of techniques. That single explanation often tips a recommendation from "lean hire" to "strong hire."

The Core Insight#

The median splits the merged array into two halves of equal size where every element on the left is less than or equal to every element on the right. We do not need to merge — we only need to find the correct cut in each array.

If we take i elements from the smaller array A and j = (m + n + 1) // 2 - i from B, the partition is valid when A[i-1] <= B[j] and B[j-1] <= A[i]. Use -inf and +inf as sentinels at the array boundaries so the comparisons stay clean. Binary search i in the smaller array to keep j non-negative.

Visual Dry Run#

Input: nums1 = [1, 3], nums2 = [2, 4, 6]. half = 3, search i in [0, 2].

Combined length 5 odd, median = max(A_left, B_left) = max(3, 2) = 3.

Solution (Optimal)#

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        A, B = nums1, nums2
        if len(A) > len(B):
            A, B = B, A
 
        m, n = len(A), len(B)
        half = (m + n + 1) // 2
        lo, hi = 0, m
 
        while lo <= hi:
            i = (lo + hi) // 2
            j = half - i
 
            a_left  = A[i - 1] if i > 0 else float('-inf')
            a_right = A[i]     if i < m else float('inf')
            b_left  = B[j - 1] if j > 0 else float('-inf')
            b_right = B[j]     if j < n else float('inf')
 
            if a_left <= b_right and b_left <= a_right:
                if (m + n) % 2 == 1:
                    return float(max(a_left, b_left))
                return (max(a_left, b_left) + min(a_right, b_right)) / 2.0
            elif a_left > b_right:
                hi = i - 1
            else:
                lo = i + 1
 
        return 0.0

var findMedianSortedArrays = function(nums1, nums2) {
    let A = nums1, B = nums2;
    if (A.length > B.length) [A, B] = [B, A];
 
    const m = A.length, n = B.length;
    const half = Math.floor((m + n + 1) / 2);
    let lo = 0, hi = m;
 
    while (lo <= hi) {
        const i = (lo + hi) >> 1;
        const j = half - i;
 
        const aLeft  = i > 0 ? A[i - 1] : -Infinity;
        const aRight = i < m ? A[i]     :  Infinity;
        const bLeft  = j > 0 ? B[j - 1] : -Infinity;
        const bRight = j < n ? B[j]     :  Infinity;
 
        if (aLeft <= bRight && bLeft <= aRight) {
            if ((m + n) % 2 === 1) return Math.max(aLeft, bLeft);
            return (Math.max(aLeft, bLeft) + Math.min(aRight, bRight)) / 2;
        } else if (aLeft > bRight) {
            hi = i - 1;
        } else {
            lo = i + 1;
        }
    }
    return 0;
};

Time: O(log(min(m, n))) — binary search runs only on the smaller array. Space: O(1) — only a handful of pointers and sentinels.

Common Mistakes#

• Searching on the larger array and letting j go negative.
• Using (m + n) // 2 instead of (m + n + 1) // 2 so odd lengths break.
• Treating the boundary as 0 instead of -inf / +inf, which silently fails on negative inputs.
• Forgetting integer division in the even case and returning an int median.
• Adding early returns inside the loop that bypass the partition invariant.

Interview Tips#

• Start by proposing the merge solution to acknowledge it, then say "but we can do log time using partitions."
• Explicitly state the invariant before coding — interviewers reward this.
• Always swap to search on the smaller array; mention it as a deliberate choice.
• Walk a tiny example through the partition before writing the final code.

Follow-up Questions#

• What if you needed the kth element instead of the median? Generalize half to k.
• How would you handle three sorted arrays? Recursive divide and conquer on the rank.
• Can the algorithm be done recursively? Yes, but iterative partitioning is cleaner.
• What changes if duplicates are allowed? Nothing — the invariant uses non-strict inequalities.
• How would you stream this if arrays are too big to fit in memory? Use external indexes and bias the partition queries toward disk locality.

Key Takeaways#

• LC 4 is solved by binary searching on the partition position, not on a value.
• Always search the smaller array so j stays non-negative and the bound is O(log(min(m, n))).
• The invariant is A[i-1] <= B[j] and B[j-1] <= A[i].
• Use -inf and +inf as boundary sentinels to avoid special cases.
• The median formula differs for odd and even total length — use (m + n + 1) // 2 for half.
• This pattern generalizes to kth smallest in two sorted arrays and split-array problems.
• It is the canonical "binary search on a structural property" interview problem.