4. Median of Two Sorted Arrays

Q: Why binary search on the smaller array?

The binary search range is [0, m] where m = smaller array length. If m < n, this is O(log m) < O(log n) — strictly better. Always swap to ensure nums1 is smaller.

Q: What does (m+n+1)/2 represent?

The number of elements in the combined left partition. Using (m+n+1)>>1 handles odd-length combined arrays by giving the left partition one extra element — the median.

hardAsked at DRW

DRW uses this as a pure algorithmic-difficulty benchmark — O(log(min(m,n))) via binary search on the smaller array. The connection to trading is direct: computing the combined median bid-ask spread from two sorted venue feeds without merging them. Sub-O(n) is the only acceptable answer.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-22

Source citations

Public interview reports confirming this problem appears in DRW loops.

Glassdoor (2026-Q1)— DRW SWE onsite candidates report Median of Two Sorted Arrays as a hard-difficulty benchmark problem, graded almost entirely on achieving the O(log(min(m,n))) bound.
Blind (2025-10)— DRW interview threads note this problem is used to distinguish candidates who know the binary-partition approach from those who only know the O(m+n) merge.

Problem

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Constraints

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

Examples

Example 1

Input

nums1 = [1,3], nums2 = [2]

Output

2.00000

Explanation: Merged array = [1,2,3], median = 2.

Example 2

Input

nums1 = [1,2], nums2 = [3,4]

Output

2.50000

Explanation: Merged array = [1,2,3,4], median = (2+3)/2 = 2.5.

Approaches

1. Binary search on the smaller array (O(log(min(m,n))))

Binary search for a partition of the smaller array such that max(left partition) ≤ min(right partition) across both arrays combined. The median is derived from the elements at the partition boundary.

Time: O(log(min(m,n)))
Space: O(1)

function findMedianSortedArrays(nums1, nums2) {
  // Ensure nums1 is the smaller array
  if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);
  const m = nums1.length, n = nums2.length;
  let lo = 0, hi = m;
  while (lo <= hi) {
    const partX = (lo + hi) >> 1;        // partition index in nums1
    const partY = ((m + n + 1) >> 1) - partX; // corresponding partition in nums2
    const maxLeftX = partX === 0 ? -Infinity : nums1[partX - 1];
    const minRightX = partX === m ? Infinity : nums1[partX];
    const maxLeftY = partY === 0 ? -Infinity : nums2[partY - 1];
    const minRightY = partY === n ? Infinity : nums2[partY];
    if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
      if ((m + n) % 2 === 1) return Math.max(maxLeftX, maxLeftY);
      return (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2;
    } else if (maxLeftX > minRightY) {
      hi = partX - 1;
    } else {
      lo = partX + 1;
    }
  }
  return 0;
}

Tradeoff: O(log(min(m,n))) time, O(1) space. The binary search operates on the smaller array. This is the only answer DRW accepts for this problem — O(m+n) merge is mentioned only to be dismissed.

DRW-specific tips

Explain the invariant before writing any code: 'I binary search for a cut in nums1 such that everything left of both cuts is ≤ everything right of both cuts. The total number of elements left of the cut equals half the combined length — this determines the cut position in nums2 given the cut position in nums1.' DRW interviewers will ask: 'What if one of the arrays is empty?' — the algorithm handles this via the -Infinity/+Infinity sentinels. They will also ask: 'What is the kth smallest element across two sorted arrays?' — a generalization of the same binary search.

Common mistakes

Starting with the O(m+n) merge and presenting it as an answer — you will be told to improve it.
Not ensuring nums1 is the smaller array — the binary search range [0, m] must cover the smaller array.
Off-by-one in the partition size calculation — partY must equal (m+n+1)/2 - partX for the left half to have the correct size.
Not handling the +Infinity/-Infinity sentinels for edge partitions (partX = 0 or partX = m).

Follow-up questions

An interviewer at DRW may pivot to one of these next:

Kth Smallest Element in Two Sorted Arrays — generalize: find the kth smallest without fully merging.
How would you find the median of k sorted arrays in O(n log k)?
What is the probability that the median of two merged uniform distributions [0,1] lies in a given subinterval?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why binary search on the smaller array?

The binary search range is [0, m] where m = smaller array length. If m < n, this is O(log m) < O(log n) — strictly better. Always swap to ensure nums1 is smaller.

What does (m+n+1)/2 represent?

The number of elements in the combined left partition. Using (m+n+1)>>1 handles odd-length combined arrays by giving the left partition one extra element — the median.

When do you return Max(maxLeftX, maxLeftY) directly vs averaging?

For odd total length, the median is the single middle element — the maximum of the left partition. For even length, it is the average of the maximum of the left and the minimum of the right partition.

Practice these live with InterviewChamp.AI

Drill Median of Two Sorted Arrays and other DRW interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →