4.11.7 — Median of Two Sorted Arrays

LeetCode 4 · Hard

The problem

Two sorted arrays. Find the median of their combined contents, in O(\log(m+n)).

nums1 = [1,3], nums2 = [2]        →  2.0      (merged: [1,2,3])
nums1 = [1,2], nums2 = [3,4]      →  2.5      (merged: [1,2,3,4])

Merging them and taking the middle is O(m+n) and is explicitly ruled out.

The pattern

The median splits the combined data into two halves of equal size, where everything in the left half is at most everything in the right half. So instead of finding a value, find the cut.

Draw a vertical line through both arrays at once:

A:  a0  a1  a2 | a3  a4
B:  b0  b1     | b2  b3  b4
    └── left ──┘└── right ──┘

Take i elements from the front of A and j from the front of B. If you want a total of half elements on the left, then j is forced:

j = \text{half} - i

That is the first key idea. You only choose i. The value of j follows, so there is one dimension to search, not two.

The second key idea is the condition for a correct cut. Everything on the left must be at most everything on the right. Within each array that is automatic, since both are sorted. What has to be checked is the two cross comparisons:

A_{\text{left}} \le B_{\text{right}} \quad\text{and}\quad B_{\text{left}} \le A_{\text{right}}

where A_left is the last element taken from A, A_right the first element left behind, and likewise for B.

If both hold, the cut is correct and the median is right there at the boundary. If A_left > B_right, you took too much from A, so move the cut left. If B_left > A_right, you took too little, so move right.

That is a monotonic condition, so binary search i.

Three details that make it work

Binary search the shorter array. Then j = half - i can never fall outside B's bounds. Search the longer one and j can go negative or past the end, and you spend the rest of your life adding guards.

Use the fence model. The cut can be anywhere from "take nothing from A" to "take all of A", which is len(A) + 1 positions for an array of length len(A). So low = 0 and high = len(A), one past the last index. Report 4 named this the fence model — you are choosing a gap between elements, not an element.

Use infinities at the edges. If i == 0 nothing was taken from A, so A_left should never block the comparison — set it to -\infty. If i == len(A) nothing is left behind, so A_right is +\infty. This removes every boundary branch, and it is the trick that turns a mess of if statements into four clean lines.

Getting the halves right

Let total = m + n and half = (total + 1) // 2.

The + 1 rounds up, which means that when the total is odd, the left side gets the extra element and the median is the largest value on the left. When the total is even, the two sides are equal and the median is the average of the largest on the left and the smallest on the right.

Doing it this way means one formula covers both cases with a single if at the end.

The solution

Python

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        A, B = (nums1, nums2) if len(nums1) <= len(nums2) else (nums2, nums1)
        total = len(A) + len(B)
        half = (total + 1) // 2

        low, high = 0, len(A)                  # fence model

        while low <= high:
            i = low + (high - low) // 2        # take i from A
            j = half - i                       # so j from B is forced

            A_left  = A[i - 1] if i > 0        else float('-inf')
            A_right = A[i]     if i < len(A)   else float('inf')
            B_left  = B[j - 1] if j > 0        else float('-inf')
            B_right = B[j]     if j < len(B)   else float('inf')

            if A_left <= B_right and B_left <= A_right:        # correct cut
                if total % 2:
                    return float(max(A_left, B_left))
                return (max(A_left, B_left) + min(A_right, B_right)) / 2

            if A_left > B_right:
                high = i - 1                   # took too much from A
            else:
                low = i + 1                    # took too little

        return 0.0

TypeScript

function findMedianSortedArrays(nums1: number[], nums2: number[]): number {
  const [A, B] = nums1.length <= nums2.length ? [nums1, nums2] : [nums2, nums1];
  const total = A.length + B.length;
  const half = Math.floor((total + 1) / 2);

  let low = 0, high = A.length;

  while (low <= high) {
    const i = low + Math.floor((high - low) / 2);
    const j = half - i;

    const aLeft  = i > 0 ? A[i - 1] : -Infinity;
    const aRight = i < A.length ? A[i] : Infinity;
    const bLeft  = j > 0 ? B[j - 1] : -Infinity;
    const bRight = j < B.length ? B[j] : Infinity;

    if (aLeft <= bRight && bLeft <= aRight) {
      if (total % 2) return Math.max(aLeft, bLeft);
      return (Math.max(aLeft, bLeft) + Math.min(aRight, bRight)) / 2;
    }

    if (aLeft > bRight) high = i - 1;
    else low = i + 1;
  }

  return 0.0;
}

Trace

A = [1, 3], B = [2]. A is already the shorter, total = 3, half = 2.

low	high	i	j	A_left	A_right	B_left	B_right	verdict
0	2	1	1	1	3	2	∞	1 ≤ ∞ ✓ and 2 ≤ 3 ✓ — correct cut

Total is odd, so the median is max(A_left, B_left) = max(1, 2) = 2. ✓

The cut takes [1] from A and [2] from B on the left, leaving [3] on the right. The merged array is [1, 2, 3] and the median is 2.

Complexity

O(\log(\min(m, n))) time — better than the required bound, because you search only the shorter array. O(1) space.

Being realistic about this problem

This is the hardest binary search commonly asked, and getting it perfect under pressure is unusual. Have a plan for partial credit.

Say the merge solution first: O(m+n), obviously correct, and it establishes that you understand the question. Then describe the cut idea in words — "the median is a cut where everything on the left is at most everything on the right, and choosing how much to take from one array forces the other" — even if the code does not come out perfectly. That description is most of the marks.

Where this goes next

• Kth Smallest Element in Two Sorted Arrays — the same cut with half replaced by k. This problem is the special case k = (m+n+1)/2, which is a good way to remember it.
• Kth Smallest in a Sorted Matrix — binary search on the value, counting how many entries fall below it. A different technique for a similar-sounding question, and worth contrasting.
• Merging in general — the fence idea appears in external sorting and in parallel merge algorithms, where two threads must be given equal work without merging first.

What the interviewer will push on

"Why does j follow from i?" The left side must hold exactly half elements, so j = half - i.

"Why search the shorter array?" So that j always stays inside B's bounds.

"Why the infinities?" They make the boundary cases obey the same comparison as everything else, removing four branches.

"Why (total + 1) // 2?" It gives the extra element to the left side when the total is odd, so one formula covers both parities.

"Can you do it in O(m+n)?" Yes, by merging — and say that first, before attempting this.

One thing to volunteer: state the two laws before writing code. "The size law fixes j once I choose i; the ordering law is the two cross comparisons." Naming them is what turns this from a memorised trick into a derivation.

Next: 4.12 goes back to first principles on recursion — what the machine is doing, how to write a recurrence you can trust, and why backtracking is depth-first search over a tree you never build.