Skip to main content

24. Median of Two Sorted Arrays

hardAsked at MercadoLibre

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 respectively, return the median of the two sorted arrays. The overall run time complexity should be O(log(m+n)).

Constraints

  • 0 <= m, 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.0

Example 2

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

Approaches

1. Merge then index

Merge both arrays into one sorted array and read the middle element(s).

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

Tradeoff:

2. Binary partition

Binary-search a partition of the smaller array such that left halves of both arrays form the lower half of the merged sequence. Median falls on the partition boundary.

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) / 2) | 0;
  let lo = 0, hi = m;
  while (lo <= hi) {
    const i = (lo + hi) >> 1, j = half - i;
    const aL = i ? a[i-1] : -Infinity, aR = i < m ? a[i] : Infinity;
    const bL = j ? b[j-1] : -Infinity, bR = j < n ? b[j] : Infinity;
    if (aL <= bR && bL <= aR) {
      if ((m + n) % 2) return Math.max(aL, bL);
      return (Math.max(aL, bL) + Math.min(aR, bR)) / 2;
    } else if (aL > bR) hi = i - 1;
    else lo = i + 1;
  }
}

Tradeoff:

MercadoLibre-specific tips

MercadoLibre fraud teams ask this to test log-time partition thinking — useful for percentile computations across two sorted streams of seller risk scores from Brazil and Argentina.

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

Practice these live with InterviewChamp.AI →