Skip to main content

24. Median of Two Sorted Arrays

hardAsked at Wise

Find the median across two sorted arrays in logarithmic time — Wise frames it as the mid-spread quote across two sorted FX order books.

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

Problem

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

Constraints

  • 0 <= m, n <= 1000
  • 1 <= m + n <= 2000
  • -10^6 <= nums[i] <= 10^6

Examples

Example 1

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

Example 2

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

Approaches

1. Merge and pick middle

Merge into one sorted array (O(m+n)) then index the middle.

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

Tradeoff:

2. Binary search the smaller array

Binary search the cut on the shorter array so the left half across both arrays has the right count and ordering. Logarithmic in the smaller size.

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, half = (m + n + 1) >> 1;
  let lo = 0, hi = m;
  while (lo <= hi){
    const i = (lo + hi) >> 1;
    const 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 ((m + n) % 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;
  }
}

Tradeoff:

Wise-specific tips

Wise wants the log-time binary-search answer because their cross-book mid-quote computation lives on the hot path — a linear scan across two order books would blow their tick budget.

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 Wise interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →