Loading section...

Median of Two Sorted Arrays

Concepts: pyMedianSortedArrays, pyPartitionBinarySearch

LeetCode 4. Median of Two Sorted Arrays. O(log(min(m,n))). This is widely considered the hardest standard binary search problem and appears at Google, Meta, and Stripe senior-level interviews. Most candidates either cannot solve it at all, or solve it in O(m+n) by merging the arrays (naive) and get partial credit. The O(log) solution requires a deeper insight, and the interview credit for explaining it clearly -- even if you do not get the code perfect -- is enormous. The Insight: Binary Search on Partition Point The median divides the combined array into two equal halves. We want to find a partition of array A at index i and a partition of array B at index j such that all elements in the left halves are <= all elements in the right halves, and the two left halves together have exactly hal