Median of Two Sorted Arrays

Reported in interviews at Bytedance Citadel D. E. Shaw PayPal Snap

Problem statement

You are given two sorted arrays $A$ of length $m$ and $B$ of length $n$ (both in non-decreasing order, possibly containing duplicates, possibly empty, not necessarily the same length, and not both empty). Find the median of the combined sorted array of $m + n$ elements.

Implement the function with signature find_median_sorted_arrays(A, B) that returns the median as a float.

Constraints:

  • $0 \le m, n \le 10^5$
  • Elements can be any integers (including duplicates)
  • Required time complexity: $O(\log \min(m, n))$
  • Required space complexity: $O(1)$

Examples:

  • $A = [1, 3]$, $B = [2]$ -- combined sorted: $[1, 2, 3]$ -- median: $2$
  • $A = [1, 2]$, $B = [3, 4]$ -- combined sorted: $[1, 2, 3, 4]$ -- median: $(2 + 3)/2 = 2.5$
  • $A = [0, 0]$, $B = [0, 0]$ -- median: $0.0$

Provide the partition-based algorithm, explain why it is correct, and handle both even and odd total lengths.

Example

find_median_sorted_arrays([1, 2], [3, 4]) -> 2.5

The combined sorted array is $[1, 2, 3, 4]$; with an even total of 4 elements the median is the average of the two middle values $(2 + 3) / 2 = 2.5$, returned as a float.

Show hint

Instead of building the merged array, what property must a cut through both arrays have for everything on its left to precede everything on its right?

Relevant roles: ML Engineer, AI Engineer, Forward Deployed Engineer and LLM Engineer.

Related free problems