Skip to main content

27. Median of Two Sorted Arrays

hardAsked at Mercury

Find the median of two sorted arrays in logarithmic time.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given two sorted arrays nums1 and nums2 of sizes m and n, return the median of the combined sorted array. The solution should run in O(log(min(m, n))) time.

Constraints

  • nums1.length + nums2.length >= 1
  • Both arrays sorted ascending
  • -10^6 <= values <= 10^6

Examples

Example 1

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

Example 2

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

Approaches

1. Merge then index

Merge into a combined sorted array, then index the middle.

Time
O(m+n)
Space
O(m+n)
const all=[...nums1,...nums2].sort((a,b)=>a-b);
const n=all.length;
return n%2? all[(n-1)>>1] : (all[n/2-1]+all[n/2])/2;

Tradeoff:

2. Binary search the smaller array partition

Binary-search the partition i in the smaller array such that left halves of both arrays form the lower half of the merged set; check the boundary inequality and slide.

Time
O(log min(m, n))
Space
O(1)
function findMedianSortedArrays(a, b) {
  if (a.length > b.length) [a, b] = [b, a];
  const m = a.length, n = b.length, total = m + n, half = (total + 1) >> 1;
  let lo = 0, hi = m;
  while (lo <= hi) {
    const i = (lo + hi) >> 1, j = half - i;
    const aL = i === 0 ? -Infinity : a[i - 1];
    const aR = i === m ? Infinity : a[i];
    const bL = j === 0 ? -Infinity : b[j - 1];
    const bR = j === n ? Infinity : b[j];
    if (aL <= bR && bL <= aR) {
      if (total % 2) return Math.max(aL, bL);
      return (Math.max(aL, bL) + Math.min(aR, bR)) / 2;
    }
    if (aL > bR) hi = i - 1; else lo = i + 1;
  }
  return 0;
}

Tradeoff:

Mercury-specific tips

Mercury asks the binary-search variant to test treasury-reporting math — finding the median of two pre-sorted batch lists (today's ACH vs. yesterday's reconciled set) without re-merging the multi-million-row stream.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →