Amazon — Find Median of Two Sorted Arrays (Binary Search O(log min(m,n)))

Problem Statement#

Given two sorted arrays nums1 and nums2 of sizes m and n, return the median of the combined sorted array. The overall run time complexity must be O(log(m+n)).

Constraints:

• 0 <= m, n <= 1000
• -10^6 <= nums1[i], nums2[i] <= 10^6
• At least one array is non-empty

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

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

Why This Problem Matters#

Find Median of Two Sorted Arrays (LeetCode 4) is consistently ranked as one of the hardest LeetCode problems and is asked by Amazon, Google, and Microsoft in senior engineer interviews. It tests binary search on an abstract criterion — not searching for a value, but searching for the correct partition point — which is a more advanced application than standard binary search.

The O(m+n) merge-then-find approach is too slow for the problem's requirements. The O(log(min(m,n))) approach binary searches on the smaller array, trying different partition points to find the one where all elements on the left are smaller than all elements on the right. This requires deep understanding of what "the median means" (the element that splits a combined sorted array into two equal halves) and how to express that as a binary search invariant.

This problem appears in Amazon final rounds and Google L5+ interviews. It is worth mastering not just as a LeetCode problem but as a demonstration of binary search mastery on abstract conditions.

The Core Insight#

Binary search on nums1 for a partition index i. For each i, compute the corresponding nums2 partition index j = (m+n+1)//2 - i. The partition is correct when:

• nums1[i-1] <= nums2[j] (left side of nums1 is not too large)
• nums2[j-1] <= nums1[i] (left side of nums2 is not too large)

If nums1[i-1] > nums2[j], move i left. If nums2[j-1] > nums1[i], move i right. The median comes from the max of the left side and min of the right side.

Always binary search on the smaller array to achieve O(log(min(m,n))).

Visual Dry Run#

nums1=[1,3], nums2=[2,4], combined=[1,2,3,4], median=2.5

Try i=1 on nums1 (len=2), j=(2+2+1)//2 - 1 = 1:

• Left: nums1[0]=1, nums2[0]=2 → max_left=2
• Right: nums1[1]=3, nums2[1]=4 → min_right=3
• Check: 1<=4 and 2<=3 → valid partition
• Median: (2+3)/2 = 2.5

Solution (Optimal)#

class Solution:
    def findMedianSortedArrays(self, nums1: list, nums2: list) -> float:
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1
 
        m, n = len(nums1), len(nums2)
        lo, hi = 0, m
 
        while lo <= hi:
            i = (lo + hi) // 2
            j = (m + n + 1) // 2 - i
 
            left1 = nums1[i - 1] if i > 0 else float('-inf')
            right1 = nums1[i] if i < m else float('inf')
            left2 = nums2[j - 1] if j > 0 else float('-inf')
            right2 = nums2[j] if j < n else float('inf')
 
            if left1 <= right2 and left2 <= right1:
                if (m + n) % 2 == 1:
                    return float(max(left1, left2))
                else:
                    return (max(left1, left2) + min(right1, right2)) / 2.0
            elif left1 > right2:
                hi = i - 1
            else:
                lo = i + 1
 
        return 0.0

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

Time: O(log(min(m,n))) — binary search on the smaller array Space: O(1) — no additional storage

Common Mistakes#

• Not swapping to ensure binary search runs on the smaller array — causes j to go negative
• Using -Infinity in Python as float('-inf') instead of comparing to None — correct in Python
• Off-by-one: j must be (m+n+1)//2 - i, not (m+n)//2 - i — the +1 handles odd total length
• Returning the wrong combination for odd vs even total length — odd: max of left sides; even: average of max_left and min_right
• Binary searching on both arrays independently — binary search on one fully determines the other

Interview Tips#

• Explain the mental model first: "The median splits the combined array into two halves; we binary search for that split"
• Use +infinity and -infinity for boundary cases — avoids verbose null checks
• Always swap to binary search on the smaller array — prevents j from becoming negative
• Trace through the first example manually before coding — builds confidence and catches edge cases
• Amazon/Google often accept the O((m+n) log(m+n)) merge approach as a starting point, then ask for O(log) optimization

Follow-up Questions#

• How do you find the kth smallest element across two sorted arrays? — Same binary search on partition; adjust half-size to k//2
• What if both arrays are very large and on disk? — External merge; binary search on file chunks
• How does this generalize to N sorted arrays? — O(log N * log total) with iterative binary search
• Can you solve this without binary search? — Merge in O(m+n), find middle; or two-pointer scan; both are O(m+n)
• What if arrays contain duplicates? — Algorithm handles duplicates correctly; no changes needed

Key Takeaways#

• Binary search on partition index i in the smaller array; j = (m+n+1)//2 - i in the larger
• The valid partition condition: left1 <= right2 and left2 <= right1
• Use +infinity/-infinity for boundary conditions when i=0, i=m, j=0, or j=n
• For odd total length: median is max(left1, left2); for even: average of max_left and min_right
• Always binary search on the smaller array to avoid negative j values and achieve O(log min(m,n))
• Amazon tests this as the canonical hard binary search problem — it separates strong candidates from exceptional ones
• This generalizes to "kth smallest element in two sorted arrays" by adjusting the half-size parameter