Skip to main content

24. Median of Two Sorted Arrays

hardAsked at Ramp

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 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, n <= 1000
  • 1 <= m + n <= 2000

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. Brute force merge

Merge both arrays into a new sorted array and read the middle.

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

Tradeoff:

2. Binary search on partition

Binary search the partition point on the shorter array such that max(leftPartitions) <= min(rightPartitions); the median is determined from those four boundary values.

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

Tradeoff:

Ramp-specific tips

Ramp likes this one because their ledger reconciliation runs streaming-median queries across sorted transaction batches — the partition-binary-search pattern signals you can hit the log target instead of merging.

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

Practice these live with InterviewChamp.AI →